<!DOCTYPE html>
<html lang="zh-cn">
  <head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta name="author" content="Zhou Wei <zromyk@163.com>">
  <title>计算机真题</title>
  <link rel="shortcut icon" href="/favicon.ico">
  <link rel="stylesheet" href="/style/html/pure.css">
  <link rel="stylesheet" href="/style/html/main.css">
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.css">
  <!-- <link rel="stylesheet" href="https://apps.bdimg.com/libs/highlight.js/9.1.0/styles/default.min.css"> -->
<link rel="stylesheet" href="/style/article/highlight/default.min.css">
<link rel="stylesheet" href="/style/article/pell-1.0.6/dist/pell.css">

</head>
<body>
  <div id="menu-background"></div>
  <div id="menu">
    <div class="pure-menu pure-menu-horizontal">
  <ul class="pure-menu-list block-middle">
    <li class="pure-menu-item">
  <a class="pure-menu-heading" href="/index.html">ZROMYK</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/index.html">主页</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/archive/index.html">归档</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/download/index.html">下载</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/feedback/index.html">反馈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/about/index.html">关于我</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="https://github.com/zromyk"><i class="fa fa-github" style="font-size:32px"></i></a>
</li>

  </ul>
</div>

  </div>
  <div id="layout">
    <div class="content">
      <div id="nav">
    <div id="navigation" class="navigation">
  <ul class="pure-menu-list">
    <li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#_1">总结</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#1">重要考点1：基本分页存储管理方式（非连续分配管理方式)</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#2">重要考点2：基本分段存储管理方式</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#3tlb">重要考点3：TLB</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#4cache">重要考点4：Cache</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#5">重要考点5：互斥访问</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#6">重要考点6：文件管理</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav3" onclick="animateByNav()" href="#7">重要考点7：无向图与有向图</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2019">2019真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4113-l-a_1a_2a_n-1a_n">41、（13分）设线性表 <script type="math/tex">L =(a_1,a_2,...,a_{n-1},a_n)</script> 采用带头结点的单链表保存，链表中结点定义如下：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4210">42、（10分）请设计一个队列，要求满足：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#438-nn3-mm1-1-pv-waitsignal">43、（8分）有 <script type="math/tex">n(n≥3)</script> 位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 <script type="math/tex">m(m≥1)</script> 个碗，每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作（ <span style="overflow-x: auto; max-width:100%; display:inline;"><code>wait()</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>signal()</code></span> 操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#447-300-10-200-512b-2">44、（7分）某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4516-fn-n-nxn-ixn-2xx2x1-fn-cf132m">45、（16分）已知 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)= n! = nx(n-I)x(n-2)x...x2x1</code></span>，计算 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)</code></span> 的C语言函数f1的源程序(阴影部分)及其在32位计算机M上的部分机器级代码如下：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#46-7-45-m-32-4-kb">46、 (7 分）对于题45，若计算机 M 的主存地址为 32 位，采用分页存储管理方式，页大小为 4 KB，则</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479-47-r-h1h4-ipr-ip-f-vlan">47、（9分）某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1~H4 的IP地址配置以及R的各接口 IP 地址配置如图中所示。现有若 f 台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。下列问题：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2018">2018真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4113nn1-532311234">41、（13分）给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求:</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4212bjcsxaqdjnnjtlwh842">42、（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光缆的铺设费用。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#438500mhzcpi4ab2mbs40mbsio32">43、（8分）假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4415cpu4444">44、（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如。题44图所示。根据题44图回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#45844">45、（8分）请根据题44图给出的虚拟储管理方式，回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4674kb64b11814b">46、（7分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#47747ip1921681024ipmtu1500bmtu800b">47、（7分）某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2017">2017真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4115">41、（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#428primmst">42、（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4313fn-sum_i0n-2i-2n1-1fncf1">43、（13分）已知<script type="math/tex">f(n) = \sum_{i=0}^n 2^i = 2^{n+1}-1</script>，计算<script type="math/tex">f(n)</script>的C语言函数f1如下：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4410m43f1">44、（10分）在按字节编址的计算机M上，题43中<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下：其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#45744m">45、（7分）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4683thread1thread2thread3pvwaitsignal">46、（8分）某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。请添加必要的信号量和P、V（或<span style="overflow-x: auto; max-width:100%; display:inline;"><code>wait()</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>signal()</code></span>）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479ngbn1000bsxyrxyxy3100mbpsrtt096mst00t1">47、（9分）甲乙双方均采用后退N帧协议（GBN）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。Sx，y和Rx，y分别表示甲方和乙方发送的数据帧，其中：x是发送序号；y是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=0.96ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中t0为初始时刻，此时甲方的发送和确认序号均为0，t1时刻甲方有足够多的数据待发送。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2016">2016真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#419334lh3websstcp20kbk1024mss1kbrtt200msh3100msss32kbstcpstcp">41、（9分）假设题33~4l图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#428kk2tktk">42、（8分）如果一棵非空k（k≥2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4315nn2aak0kna1a2n1n2a1a2s1s2n1-n2s1-s2">43、（15分）已知由n（n≥2）个正整数构成的集合A={ak}0≤k&lt;n}，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#449cpu50mhzcpi4d7ascii11dio05ms">44、（9分）假定CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，<u>从D接收启动命令到字符送入I/O端口需要0.5ms</u>。请回答下列问题，要求说明理由。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#451432248kbtlbcache64kb264b">45、（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#466prioritynicecputimewaittime0cputime1waittime0cputime0waittime1">46、（6分）某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4794kbfat">47、（9分）某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2015">2015真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4115mdataheadhead">41、（15分）用单链表保存m个整数，结点的结构为：时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如下：则删除结点后的head为：要习之：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4285g">42、（8分）已知含有5个顶点的图G如下图所示。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4313161616cpur0r3tsrmovleftright3sropsrsroutaluamovaabaddabsubabandaboranotaline7aluop">43、（13分）某16位计算机的主存按字节编址，存取单位为16位；采用16位定长指令字格式；CPU采用单总线结构，主要部分如下图所示。图中R0~R3为通用寄存器；T为暂存器；SR为移位寄存器，可实现直送（mov）、左移一位（left）和右移一位（right）3种操作，控制信号为SRop，SR的输出由信号SRout控制；ALU可实现直送A（mova）、A加B（add）、A减B（sub）、A与B（and）、A或B（or）、非A（not）、A加l（ine）7种操作，控制信号为ALUop。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#44104344a44a44b01r0r30123">44、（10分）<u>题43中描述的计算机</u>，其部分指令执行过程的控制信号如题44图a所示。题44图a部分指令的控制信号。该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0~R3的编号分别为0、1、2和3。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#459abambnax0xmby0yn1abpvwaitsignal">45、（9分）有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放人对方的信箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0&lt;x&lt;M），B的信箱中有y个邮件（0&lt;y&lt;N）。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或wait、signal）操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#466">46、（6分）某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#47947dhcpwww1ip2ndhcpip">47、（9分）某网络拓扑如题47图所示，其中路由器内网接口、DHCP服务器、WWW服务器与主机1均采用静态IP地址配置，相关地址信息见图中标注；主机2~主机N通过DHCP服务器动态获取IP地址等配置信息。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2014">2014真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4113wpltweightrootttwpl">41、（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4210ospf42r1lsi4242r1">42、（10分）某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表及R1的接口名构造出来的网络拓扑。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#43942">43、（9分）请根据题42描述的网络，继续回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4412pforint-i-0-i-n-isum-aisumir1r2nr6ar3p08048100h">44、（12分）某程序中有如下循环代码段p：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>for（int i = 0; i &lt; N; i++）sum += A[i];</code></span>。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为08048100H，对应的汇编代码和机器代码如下表所示。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4544mpmpr1r20r61000cachea">45、假设对于44题中的计算机M和程序P的机器代码，M采用页式虚拟存储管理；P开始执行时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>(R1)=(R2)=0,(R6)=1000</code></span>，其机器代码已调入主存但不在Cache中；数组A未调入主存，且所有数组元素在同一页，并存储在磁盘同一个扇区。请回答下列问题并说明理由。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#46f2001f30">46、文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入到文件F中，作为其第30条记录。请回答下列问题，并说明理由。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#47100010-p-vwaitsignal">47、系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>P, V(wait()，signal())</code></span> 操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2013">2013真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#41-a-0-5-5-3-5-7-5-5-5-a-0-5-5-3-5-1-5-7-aana-1">41、例如 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>A = (0, 5, 5, 3, 5, 7, 5, 5)</code></span> , 侧5为主元素；又如 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>A = (0, 5, 5, 3, 5, 1, 5, 7)</code></span> ，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#42104s-do-for-repeat-whilep1035-p2015-p3015p4035s422">42、（10分）设包含4个数据元素的集合<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S = {"do", "for", "repeat", "while"}</code></span>，各元素的查找概率依次为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>p1=0.35, p2=0.15, p3=0.15，p4=0.35</code></span>。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#43932cpu800mhzcachecpi4cache3283240ns32200mhz3232">43、（9分）某32位计算机，CPU主频为800MHz，Cache命中时的CPI为4，Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns；存储器总线宽度为32位，总线时钟频率为200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#441416cpucfzfnf00000-op-cz-n-cfzf-nf-1-1-c1z0n1-cf-nf-cf1-nf1-offset-pc22offset-pc2">44、（14分）某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位/借位标志CF、零标志ZF和符号标志NF。假定为该机设计了条件转移指令，其格式如下，其中，00000 为操作码 OP; C、Z 和 N 分别为 CF、ZF 和 NF 的对应检测位，某检测位为 1 时表示需检测对应标志，需检测的标志位中只要有一个为 1 就转移，否则不转移，例如，若 C=1，Z=0，N=1，则需检测 CF 和 NF 的值，当 CF=1 或 NF=1 时发生转移; OFFSET 是相对偏移量，用补码表示。转移执行时，转移目标地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2+2×OFFSET</code></span> ; 顺序执行时，下条指令地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2</code></span>。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#457500pvwaitsignal">45、（7分）某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：请添加必要的信号量和P、V（或wait（）、signal（）操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#468324">46、（8分）某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479internet47asir1as2r2r33r2r1r3ip47">47、（9分）假设Internet的两个自治系统构成的网络如题47图所示，自治系统ASI由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口IP地址如题47图所示。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2012">2012真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#416abcdef1035405060200561">41、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请问答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#42loadingbeingstr1str2str1str2ip">42、假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#43cpu80mhzcpi415cache516bcache9932">43、假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，主存与Cache之间5交换的块大小为16B，Cache的命中率为99%，存储器总线宽带为32位。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4416cachecache44rsrdmemxxx5ifidexmwb">44、某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，（x）表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#450532152141p11320406111013214">45、某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的&lt;虚拟页号，访问时刻&gt;是：&lt;1，1&gt;、&lt;3，2&gt;、&lt;0，4&gt;、&lt;0，6&gt;、&lt;1，11&gt;、&lt;0，13&gt;、&lt;2，14&gt;。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#464tb1tb2401kbfcb512b">46、某文件系统空间的最大容量为4TB（1TB=240），以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#47hinternetip19216808sip211687180hstcph5ip47-a">47、主机H通过快速以太网连接Internet，IP地址为192.168.0.8，服务器S的IP地址为211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2011">2011真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#418605ga">41、（8分）已知有6个顶点（顶点编号为0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4215ll1sl2ss11113151719s115s2246820s1s211abab">42、（15分）一个长度为L（L≥1）的升序序列S，处在第L/2个位置的数称为S的中位数。例如，若序列S1=（11，13，15，17，19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#43118c88r1r8xymnz1z2k1k2">43、（11分）假定在一个8位字长的计算机中运行如下类C程序段：若编译器编译时将8个8位寄存器R1~R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#441216mb1mb4kbcache8cache32bcache44-a44-b">44、（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。请回答下列问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#458110pvwaitsignal">45、（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：请添加必要的信号量和P、V（或wait（）、signal（））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#467">46、（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479mac00-15-c5-c1-5e-28ip10212810047-a47-bweb180ascii">47、（9分）某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个字节的十六进制及ASCII码内容。请参考图中的数据回答以下问题。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2010">2010真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4110783011189140hkeykeyx3mod707">41、（10分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H（key）=（keyx3）MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4213nn1rrp0pnrx0x1xn-1xpxp1xn-1x0x1xp-1">42、（13分）设将n（n&gt;1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0&lt;p&lt;n）个位置，即将R中的数据由（X0，X1&hellip;Xn-1）变换为（Xp，Xp+1&hellip;Xn-1，X0，X1&hellip;Xp-1）。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#431116128kb">43、（11分）某计算机字长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如下：转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：请回答下列问题：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4412256mbcachecache8cachecache64bcacheabint32ijsuma320">44、（12分）某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：假定int类型数据用32位补码表示，程序编译时i，j，sum均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#457cscan2kb16384">45、（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#46864kb6page1kb4pageframe26026017cah">46、（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479csmacd10mbps2km200000kms">47、（9分）某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10Mbps，主机甲和主机乙之间的距离为2km，信号传播速度是200000km/s。请回答下列问题，要求说明理由或写出计算过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav1" onclick="animateByNav()" href="#2009">2009真题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4110">41、（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4215listkkdata10">42、（15分）已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#438cpu500mhzcpi5505mbs32182">43、（8分）某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4413161610mdrine1dbmdrmdrin1mdrmaraddr1r0r0r1r1r0r1r1">44、（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD（R1），R0”的功能为（R0）+（（R1））（R1），即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格..列出指令执行阶段每个节拍的功能和有效控制信号。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#457p1p2p3nn0p1produceputp2getoddcountoddp3getevencounteven">45、（7分）三个进程P1、P2、P3互斥使用一个包含N（N&gt;0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#4684kb100nstlb10ns108nstlb2lru1tlb2tlbtlbtlb302362h1565h25a5h">46、（8分）请求分页管理系统中，假设某进程的页表内容如下表所示：页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设1TLB初始为空；2地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；3有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#479r1e1e212l0r2r2r1l0ip20211821r2l0ip20211822l1ip130111201e0ip20211831ip20211832r1r2">47、（9分）某网络拓扑如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1；R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。R1和R2的路由表结构为：</a>
</li>

  </ul>
</div>

</div>
<div id="content-articles">
  <h1 id="计算机真题" class="content-subhead">计算机真题</h1>
  <p>
    <span>1970-01-01</span>
    <span><span class="post-category post-category-cs">CS</span></span>
    <button id="button-markdownEditor" class="pure-button" onclick="markdownEditor()">启用编辑</button>
    <button id="button-save" class="pure-button" onclick="save()">保存</button>
  </p>
  <div id="content-articles-markdownEditor" style="display: none;">
    <h1>编辑 power by pell</h1>
    <div id="editor" class="pell"></div>
    <div style="margin-top:20px;">
        <h3>Text output:</h3>
        <div id="text-output"></div>
    </div>
    <div style="margin-top:20px;">
        <h3>HTML output:</h3>
        <pre id="html-output"></pre>
    </div>
  </div>
  <div id="content-articles-markdown">
    <h1 id="_1">总结</h1>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/3A01E725146BE536E8727AF86F1403FA-8551170.jpg" alt="3A01E725146BE536E8727AF86F1403FA" style="zoom:50%;" /></p>
<h3 id="1">重要考点1：基本分页存储管理方式（非连续分配管理方式)</h3>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/IMG_0261.jpg" alt="IMG_0261" style="zoom:50%;" /></p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>基本分页存储管理方式</th>
</tr>
</thead>
<tbody>
<tr>
<td>页</td>
<td>将 <strong>逻辑地址</strong> 划分为同等大小的部分。</td>
</tr>
<tr>
<td>块/页框</td>
<td>把 <strong>物理内存</strong> 划分为同大小的连续的部分。<strong>页和页框的大小相等</strong>。</td>
</tr>
<tr>
<td>大小</td>
<td>页内偏移量一般为 <script type="math/tex">12bit</script>，即可以表示  <script type="math/tex">2^{12}</script> 个地址。<br />若计算机按字节<script type="math/tex">B</script>寻址，则页的大小为 <script type="math/tex">2^{12}B=4KB</script>
</td>
</tr>
<tr>
<td>数量</td>
<td>
<script type="math/tex">\cfrac{逻辑地址位决定逻辑空间的大小}{页内偏移量位决定页的大小}=\cfrac{2^{32}}{2^{12}}=2^{20}</script> 页</td>
</tr>
<tr>
<td>一级页表</td>
<td><strong>一级页表的分页存储管理方式</strong>：<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2021-12-05 21.55.54.png" alt="截屏2021-12-05 21.55.54" style="zoom:80%;" /><br /><br />页号：页索引。<br />页内偏移量：页 ( 块/页框 ) 内的逻辑 ( 物理 ) 地址偏移量。<br /></td>
</tr>
<tr>
<td>二级页表</td>
<td><strong>二级页表的分页存储管理方式</strong>：<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2021-12-05 21.57.28.png" alt="截屏2021-12-05 21.57.28" style="zoom:46%;" /><br /><br />页目录号：一级页表索引。（一级页表的页表项：二级页表索引）<br />页表索引：二级页表索引。（二级页表的页表项：页框索引）<br />页内偏移量：页 ( 块/页框 ) 内的逻辑 ( 物理 ) 地址偏移量。<br /><br />一级页表（页目录：二级页表的目录）：存储了 [页目录号] 和二级页表的对应关系的页表。<br /><script type="math/tex; mode=display">\left[\begin{array}{c c}页表项编号(不占空间) & 内容:地址(32bit) \\ \hline 页目录号1 & 二级页表索引地址1\\ 页目录号2 & 二级页表索引地址2\\ 页目录号3 & 二级页表索引地址3\\ 页目录号4 & 二级页表索引地址4\end{array}\right]</script><br /> <br />二级页表：存储 [页表索引] 和块/页框的对应关系的页表。<br /><script type="math/tex; mode=display">\left[\begin{array}{c c}页表项编号(不占空间)& 内容:地址(32bit) \\ \hline 页表索引1 & 页框地址1\\ 页表索引2 & 页框地址2\\ 页表索引3 & 页框地址3\\ 页表索引4 & 页框地址4\end{array}\right]</script><br /><br />页表：<script type="math/tex">1张一级页表 + 1024张二级页表 = 1025张页</script><br /><br /><strong>页目录和页表占用空间</strong>：<br />1. 各级页表的大小不能超过一个页面。<br />2. 一般来说页面的大小为 <script type="math/tex">2^{12}B=4KB</script>，页表项的大小为 <script type="math/tex">4B</script> .<br />3. 因此，一般一个页面可以有 <script type="math/tex">1K = 2^{10}</script> 个页表项，需要用 <script type="math/tex">10bit</script> 来表示。<br /><br />&gt; 举例虚拟地址为40bit，则虚拟地址的逻辑结构：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[一级页号 8][二级页号 10][三级页号 10][页内偏移 12]</code></span><br /></td>
</tr>
</tbody>
</table></div>
<h3 id="2">重要考点2：基本分段存储管理方式</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>基本分段存储管理方式</th>
</tr>
</thead>
<tbody>
<tr>
<td>虚拟地址结构</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-11-17 22.02.57.png" alt="截屏2020-11-17 22.02.57" style="zoom:67%;" /></td>
</tr>
<tr>
<td>段号</td>
<td>决定段的数量，<script type="math/tex">2^{16}=64K</script> 个段</td>
</tr>
<tr>
<td>段内地址</td>
<td>决定段的最大长度，<script type="math/tex">2^{16}=64K</script> 个地址。<br />若计算机按字节<script type="math/tex">B</script>寻址，则段的最大长度为 <script type="math/tex">64KB</script>
</td>
</tr>
<tr>
<td>段表</td>
<td>
<script type="math/tex; mode=display">\left[\begin{array}{c c c}段表项编号(不占空间) & 内容:段长(16bit) & 内容:段基址(32bit)\\ \hline 段编号1 & 段长1 & 段基址1\\ 段编号2 & 段长2 & 段基址2\\ 段编号3 & 段长3 & 段基址3\\ 段编号4 & 段长4 & 段基址4\end{array}\right]</script>
</td>
</tr>
</tbody>
</table></div>
<h3 id="3tlb">重要考点3：TLB</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>快表 TLB</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>示例图</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 20.56.33.png" alt="截屏2020-12-21 20.56.33" style="zoom:35%;" /></td>
</tr>
<tr>
<td>逻辑结构</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag][有效位][实页号]</code></span></td>
</tr>
</tbody>
</table></div>
<h3 id="4cache">重要考点4：Cache</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>Cache</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>示例图</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 20.34.06.png" alt="截屏2020-12-21 20.34.06" style="zoom: 25%;" /></td>
</tr>
<tr>
<td>组相联映射地址结构</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>物理地址 = [标记][Cache组号][块内地址]</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
</tr>
<tr>
<td>Cache总容量</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>行数 * (Tag + [LRU位] + [脏位] + 有效位 + 一个块保存数据大小)</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>行数</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>组数(图中为3bit，即8组) * 每组行数(图中为2行)</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag</code></span></td>
<td>与物理地址有关，图中为 <script type="math/tex">20bit</script>
</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[LRU位]</code></span></td>
<td>最近最少使用算法，2 组 Cache 则有 1 位LRU位， 4 组 Cache 则有 2 位LRU位&hellip;</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[脏位]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>直写法(无), 回写法(1bit)</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>有效位</code></span></td>
<td>
<script type="math/tex">1bit</script>
</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>一个块保存数据大小</code></span></td>
<td>
<script type="math/tex">块内地址(5bit)</script>：表示 <script type="math/tex">2^5=32</script> 个地址，计算机按字节编址。则一个块的大小为 <script type="math/tex">32B</script>
</td>
</tr>
</tbody>
</table></div>
<h3 id="5">重要考点5：互斥访问</h3>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>semaphore mutex; // 信号定义
</code></span></code></pre>
<h3 id="6">重要考点6：文件管理</h3>
<h3 id="7">重要考点7：无向图与有向图</h3>
<p>邻接矩阵</p>
<p>邻接表</p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Prim</code></span> 算法</p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Kruskal</code></span> 算法</p>
<h1 id="2019">2019真题</h1>
<h5 id="4113-l-a_1a_2a_n-1a_n">41、（13分）设线性表 <script type="math/tex">L =(a_1,a_2,...,a_{n-1},a_n)</script> 采用带头结点的单链表保存，链表中结点定义如下：</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">typedef struct node
{
    int data;
    struct node * next;
}NODE;
</code></span></code></pre>
<p>请设计一个空间复杂度为 <script type="math/tex">O(1)</script> 且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表 <script type="math/tex">L =(a_1,a_n,a_2,a_{n-1},...)</script>
</p>
<p>要求：</p>
<p>（1）给出算法的基本设计思想.</p>
<p>（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</p>
<p>（3）说明你所设计的算法的时间复杂度。</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef struct node
{
    int data;
    struct node *next;
}NODE;

void SetData(NODE **list, int data)
{
    (*list) = (NODE *)malloc(sizeof(NODE));
    (*list)-&gt;data = data;
    (*list)-&gt;next = NULL;
}

void ShowList(NODE *list)
{
    while (list != NULL &amp;&amp; list-&gt;next != NULL) {
        printf(&quot;%d-&gt;&quot;, list-&gt;data);
        list = list-&gt;next;
    }
    if (list != NULL) {
        printf(&quot;%d-&gt;NULL\n&quot;, list-&gt;data);
    }
}

/* 需要的算法 */
void flod(NODE *list)
{
    // STEP1：找到链表的中间结点，1，2，3，4，5
    NODE *mid, *end;

    mid = end = list;
    while (end-&gt;next != NULL) {
        mid = mid-&gt;next;
        end = end-&gt;next;
        if (end != NULL) {
            end = end-&gt;next;
        }
    }
    // 结果：得到 mid 指向第 n/2+1 个结点，end 指向链表末尾结点

    // STEP2：将后半链表翻转
    NODE *temp, *curr, *newNext;

    curr = mid-&gt;next;           // curr 指向每次需要翻转的当前结点
    mid-&gt;next = NULL;           // 将前半段的末尾结点的 newNext 指针指向 NULL
    newNext = NULL;             // newNext 为当前结点的重设 newNext 结点
    while (curr != NULL) {
        temp = curr-&gt;next;      // temp 暂存当前结点的下一个结点
        curr-&gt;next = newNext;   // 当前结点的 newNext 为之前设置的 newNext
        newNext = curr;         // 下一个结点的 newNext 为当前结点
        curr = temp;            // 当前结点更新为上一结点的 newNext 结点    
    }
    // 结果：curr 指向 NULL, newNext 指向 后半段链表倒转后的首结点

    // STEP3：使用 list 和 newNext 指针合并两个链表
    NODE *head = newNext;      // 重命名 newNext 为 head

    while (head != NULL) {
        temp = head-&gt;next;
        head-&gt;next = list-&gt;next;
        list-&gt;next = head;
        list = head-&gt;next;
        head = temp;
    }
}
/* 需要的算法 */

int main(int argc, char const *argv[])
{
    NODE *list;

    SetData(&amp;list, 1);
    SetData(&amp;list-&gt;next, 2);
    SetData(&amp;list-&gt;next-&gt;next, 3);
    SetData(&amp;list-&gt;next-&gt;next-&gt;next, 4);
    SetData(&amp;list-&gt;next-&gt;next-&gt;next-&gt;next, 5);
    SetData(&amp;list-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next, 6);
    SetData(&amp;list-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next, 7);

    ShowList(list);
    flod(list);
    ShowList(list);

    return 0;
}
</code></span></code></pre>
<h5 id="4210">42、（10分）请设计一个队列，要求满足：</h5>
<ol>
<li>初始时队列为空；</li>
<li>入队时，允许增加队列占用空间；</li>
<li>出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；</li>
<li>入队操作和出队操作的时间复杂度始终保持为 <script type="math/tex">O(1)</script>。</li>
</ol>
<p>请回答下列问题：</p>
<h6 id="1_1">（1）该队列应该选择链式存储结构，还是顺序存储结构？</h6>
<ul>
<li>采用链式存储结构(两段式单向循环链表)，队头指针为front，队尾指针为rear。</li>
</ul>
<h6 id="2_1">（2）画出队列的初始状态，并给出判断队空和队满的条件。</h6>
<ul>
<li>
<p>初始时，创建只有一个空闲结点的两段式单向循环链表，头指针front与尾指针rear均指向空闲结点。如下图所示：</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-23 18.48.28.png" alt="截屏2020-12-23 18.48.28" style="zoom:67%;" /></p>
</li>
</ul>
<h6 id="3">（3）画出第一个元素人队后的队列状态。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-23 18.49.10.png" alt="截屏2020-12-23 18.49.10" style="zoom:67%;" /></p>
<h6 id="4">（4）给出入队操作和出队操作的基本过程。</h6>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">人队操作:
若(front == rear-&gt;nexl) //队满
    则在 rear 后面插入一个新的空闲结点;
入队元素保存到 rear 所指结点中; 
rear = rear-&gt;nexl;
返回;

------------------------------------------------------------------------
出队操作:
若(front == rear) //队空
    则出队失败,返回;
取 front 所指结点中的元素e;
front = front-&gt;next;
返回e;
</code></span></code></pre>
<h5 id="438-nn3-mm1-1-pv-waitsignal">43、（8分）有 <script type="math/tex">n(n≥3)</script> 位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 <script type="math/tex">m(m≥1)</script> 个碗，每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作（ <span style="overflow-x: auto; max-width:100%; display:inline;"><code>wait()</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>signal()</code></span> 操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">semaphore bowl = min(n-1, m);
semaphore chopsticks[n];

for (int i = 0; i &lt; n; i++) {
    chopsticks[n] = 1;
}

// 哲学家 i 的程序
while (True) {
    思考;
    P(bowl);
    P(chopsticks[i]);           // 取左边筷子
    P(chopsticks[i+1] mod n);   // 取右边筷子
    就餐;
    V(chopsticks[i+1] mod n);
    V(chopsticks[i]);
    V(bowl);
}
</code></span></code></pre>
<h5 id="447-300-10-200-512b-2">44、（7分）某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：</h5>
<h6 id="1_2">（1）磁盘的容量是多少？</h6>
<ul>
<li>
<script type="math/tex">300*10*200*512B=300000*1024B=3*10^5KB</script>
</li>
</ul>
<h6 id="2-85-410026060005101660110560-sstf">（2）假设磁头在 85 号柱面上，此时有4个磁盘访问请求，簇号分别为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>100260</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>60005</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>101660</code></span>和<span style="overflow-x: auto; max-width:100%; display:inline;"><code>110560</code></span>。若采用最短寻道时间优先（ SSTF）调度算法，则系统访问簇的先后次序是什么？</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>100260</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>60005</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>101660</code></span> 和 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>110560</code></span> 的柱面号分别是 100，60，101，110</li>
<li>则系统访问簇的先后次序是：100260，101660，110560，60005</li>
</ul>
<h6 id="3-100530-i0">（3）第 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>100530</code></span> 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由I/0系统的什么程序完成的？</h6>
<ul>
<li>柱面号：<script type="math/tex">\cfrac{100530}{10*200/2}=100</script>
</li>
<li>磁道号：<script type="math/tex">\cfrac{(100530)\ mod\ (10*200/2)}{200/2}=\cfrac{530}{100}=5</script>
</li>
<li>扇区号：<script type="math/tex">(530\ mod\ (200/2))*2=60</script>
</li>
</ul>
<h5 id="4516-fn-n-nxn-ixn-2xx2x1-fn-cf132m">45、（16分）已知 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)= n! = nx(n-I)x(n-2)x...x2x1</code></span>，计算 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)</code></span> 的C语言函数f1的源程序(阴影部分)及其在32位计算机M上的部分机器级代码如下：</h5>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>序号</th>
<th>地址</th>
<th>机器码</th>
<th>意义</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>int fl(int n){</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>1</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401000</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>55</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>push ebp</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>if( n&gt;1 )</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>11</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401018</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>83 7D 08 01</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>cmp,dword ptr [ebp+8],1</code></span></td>
</tr>
<tr>
<td>12</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040101C</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>7E 17</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>jle f1+35h ( 00401035 )</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>return n * fl(n-1);</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>13</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040101E</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>8B 45 08</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>mov eax，dword，ptr[ebp+8]</code></span></td>
</tr>
<tr>
<td>14</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401021</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>83 E8 01</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>sub eax,1</code></span></td>
</tr>
<tr>
<td>15</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401024</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>50</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>push eax</code></span></td>
</tr>
<tr>
<td>16</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401025</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>E8 D6 FF FF FF</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>call fl (00401 000)</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>19</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401030</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0F AF C1</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>imul eax,ecx</code></span></td>
</tr>
<tr>
<td>20</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401033</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>EB 05</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>jmp f1+3Ah (0040103a)</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>else return 1;</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>21</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401035</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>B8 01 00 00 00</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>mov eax,1</code></span></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>26</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401040</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>3B EC</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>cmp ebp,esp</code></span></td>
</tr>
<tr>
<td>30</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040104A</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>C3</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>ret</code></span></td>
</tr>
</tbody>
</table></div>
<p>其中，机器级代码行包括行号虚拟地址、机器指令和汇编指令，计算机M按字节编址，int型数据占32位。请回答下列问题：</p>
<h6 id="1-f10-f1-f1">（1）计算 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(10)</code></span> 需要调用函数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span> 多少次？执行哪条指令会递归调用 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span> ？</h6>
<ul>
<li>需要调用 f1 函数 10次，第16条指令 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>call fl (00401 000)</code></span> 会调用 f1</li>
</ul>
<h6 id="2_2">（2）上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？</h6>
<ul>
<li>条件转移指令：第12条 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>jle f1+35h ( 00401035 )</code></span></li>
<li>一定会使程序跳转执行的指令：<ul>
<li>第16条 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>jle f1+35h ( 00401035 )</code></span></li>
<li>第20条 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>jmp f1+3Ah (0040103a)</code></span></li>
<li>第30条 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>ret</code></span></li>
</ul>
</li>
</ul>
<h6 id="3-16-call-17-16-call-16-call-4-m">（3）根据第 16 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>call</code></span> 指令，第 17 行指令的虚拟地址应是多少？已知第 16 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>call</code></span> 指令采用相对寻址方式，该指令中的偏移量应是多少(给出计算过程)？已知第 16 行 call 指令的后 4 字节为偏移量，M采用大端还是小端方式？</h6>
<ul>
<li>第 16 行指令占 5B，则第 17 行指令的虚拟地址是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040102A</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040 1000H = 0040 1025H + 5H + 偏移量</code></span>，偏移量：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>-2AH = FFFF FFD6H</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[E8][D6 FF FF FF]</code></span>，M采用小端方式。</li>
</ul>
<h6 id="4-f13-6-227-020800-f113-1-932-053-504-f113-f1">（4） <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(13)= 6 227 020800</code></span>，但 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(13)</code></span> 的返回值为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 932 053 504</code></span>，为什么两者不相等？要使 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(13)</code></span> 能返回正确的结果，应如何修改 f1 源程序？</h6>
<ul>
<li>
<script type="math/tex">2^{32}=4,294,967,296<6,227,020,800</script>，在计算过程中 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>int</code></span> 类型变量溢出。</li>
<li>可以将函数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span> 中的 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>int</code></span> 类型改为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>long long、double、float</code></span></li>
</ul>
<h6 id="5-19-inrecx-32-of1-cpu-imul">（5）第 19 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>inR[ecx]</code></span>，当乘法器输出的高，低 32 位乘积之间满足什么条件时，溢出标志 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>OF=1</code></span> ？要使CPU在发生溢出时转异常处理，编泽器应在 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>imul</code></span> 指令后加一条什么指令？</h6>
<ul>
<li>若乘积的高 33 位为非全 0 或非全 l ，则 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>OF=1</code></span>，编译器应该在 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>imul</code></span> 指令后加一条 “ 溢出自陷指令 ” ，使得 CPU 自动查询溢出标志 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>OF</code></span> ，当 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>OF=1</code></span> 时调出 “ 溢出异常处理程序 ” 。</li>
</ul>
<blockquote class="content-quote">
<p>和 MUL 指令一样，其乘积的存储大小使得溢出不会发生。同时，如果乘积的 <u>高半部分不是其低半部分的符号扩展（即高半部分+低半部分的符号位，不完全一致，非全1或非全0）</u>，则进位标志位和溢出标志位置 1。</p>
</blockquote>
<h5 id="46-7-45-m-32-4-kb">46、 (7 分）对于题45，若计算机 M 的主存地址为 32 位，采用分页存储管理方式，页大小为 4 KB，则</h5>
<ul>
<li><strong>第 1 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>push</code></span> 指令和第 30 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>ret</code></span> 指令是否在同一页中(说明理由)？</strong><ul>
<li>第 1 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>push</code></span> 指令的地址 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401000</code></span>，第 30 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>ret</code></span> 指令的地址 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040104A</code></span>，地址之差 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>4A H = 74 D</code></span>，计算机按字节编址，<script type="math/tex">74B < 4KB</script>。（不完全正确，应该看地址的高位）</li>
<li>页的大小为 <script type="math/tex">4KB=2^{12}</script>，因此，地址的高20位为页号，从题45的表格中得这两条地址的高20bit相同，故它们在同一页中。</li>
</ul>
</li>
<li><strong>若指令 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>Cache</code></span> 有64行，采用4路组相联映射方式，主存块大小为 64 B，则 32 位主存地址中，哪几位表示块内地址？哪儿位表示 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>Cache</code></span> 组号？哪几位表示标记(<span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag</code></span>)信息？</strong><ul>
<li>贮存块的大小为 64B，需要用 6bit 来表示。</li>
<li>Cache有 64 行，4路，则有 16 组，需要用 4bit 来表示。</li>
<li>因此，高 22bit 表示 Tag，然后 4bit 表示 Cache 组号，最后低 6bit 表示块内地址。</li>
<li>即， <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag 22bit][组号 4bit][块内地址 6bit]</code></span></li>
</ul>
</li>
<li><strong>读取第 16 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>call</code></span> 指令时，只可能在指令 Cache 的哪一组中命中(说明理由)？</strong><ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401025</code></span> 指令的二进制表示为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0000 0000 0100 0000 0001 00[00 00]10 0101</code></span></li>
<li>表示组号的那 4bit 为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0000</code></span> ，所以 Cache 只能在第 0 组命中。</li>
</ul>
</li>
</ul>
<h5 id="479-47-r-h1h4-ipr-ip-f-vlan">47、（9分）某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1~H4 的IP地址配置以及R的各接口 IP 地址配置如图中所示。现有若 f 台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。下列问题：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-23 16.14.03.png" alt="截屏2020-12-23 16.14.03" style="zoom:50%;" /></p>
<h6 id="1123">（1）设备1、设备2和设备3分别应选择什么类型网络设备？</h6>
<ul>
<li>H1 和 H2 的聚合子网 IP 相同，H3 和 H4 的聚合网 IP 相同，因此设备1为路由器，设备2、设备3为以太网交换机。</li>
</ul>
<h6 id="2123ipip">（2）设备1、设备2和设备3中，哪几个设备的接口需要配置IP地址？并为对应的接口配置正确的IP地址。</h6>
<ul>
<li>设备1需要配置 IP 地址。</li>
<li>IF1 应该配置的 IP 地址为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.254</code></span>（192.168.1.253/30 所在子网只能表示 4 个 IP地址，一个为本网络地址 192.168.1.252，一个为广播地址 192.168.1.255，另一个 192.168.1.253 已经被占用）</li>
<li>IF2 应该配置的 IP 地址为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.1</code></span>，，即 H1 和 H2 的默认网关。</li>
<li>IF3 应该配置的 IP 地址为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.65​</code></span>，即 H3 和 H4 的默认网关。</li>
</ul>
<h6 id="3-h1h4-internetr">（3）为确保主机 H1~H4 能够访问 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>Internet</code></span>，R需要提供什么服务？</h6>
<ul>
<li>R 需要提供 NAT 服务（网络地址转换服务）</li>
</ul>
<h6 id="4h3-1921681127-ip">（4）若主机H3发送一个目的地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.127</code></span> 的IP数据报，网络中哪几个主机会接收该数据报？</h6>
<ul>
<li>192.168.1.127 属于 192.168.1.66/26，因此网络中 H4 能够接收到该数据报。<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.127/26 = [ 192.168.1.01 ] 11 1111</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>192.168.1.66/26 = [ 192.168.1.01 ] 00 0010</code></span></li>
</ul>
</li>
</ul>
<h1 id="2018">2018真题</h1>
<h5 id="4113nn1-532311234">41、（13分）给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求:</h5>
<p>（1）给出算法的基本设计思想。</p>
<p>（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</p>
<p>（3）说明你所设计算法的时间复杂度和空间复杂度。</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">int findMinNum(const int input[], int n)
{
    int i;
    int *sign;

    sign = (int *)malloc(sizeof(int) * n);
    menset(sign, 0, sizeof(int) * n);

    for (i = 0; i &lt; n; ++i) {
        if (0 &lt; input[i] &amp;&amp; input[i] &lt;= n) {
            sign[input[i]-1] = 1;
        }
    }
    for (i = 0; i &lt; n; ++i) {
        if (sign[input[i]] == 0) {
            break;
        }
    }
    return i + 1;
}
</code></span></code></pre>
<h5 id="4212bjcsxaqdjnnjtlwh842">42、（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光缆的铺设费用。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 09.19.34.png" alt="截屏2020-12-16 09.19.34" style="zoom: 33%;" /></p>
<h6 id="1_3">（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。</h6>
<p>为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动 prim 算法或 kruskal 算法作图。注意本题最小生成树有两种构造，如下图所示。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-23 00.14.39.png" alt="截屏2020-12-23 00.14.39" style="zoom:50%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 10.24.16.png" alt="截屏2020-12-16 10.24.16" style="zoom:50%;" /></p>
<h6 id="2421">（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。</h6>
<ul>
<li>
<p>邻接矩阵、邻接表、邻接多重表</p>
</li>
<li>
<p>Prim算法和Kruskal算法</p>
</li>
</ul>
<h6 id="31h1tlh2bjh1h2ttl5iph2ip">（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？</h6>
<ul>
<li>对于图1，分组到达XA时TTL=1，处理之后TTL=0，会被XA丢弃，分组无法到达H2</li>
<li>对于图2，分组可以到达H2</li>
</ul>
<h5 id="438500mhzcpi4ab2mbs40mbsio32">43、（8分）假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。</h5>
<h6 id="1aio10acpuacpu">（1）若设备A采用定时查询I/O方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百分比至少是多少？</h6>
<blockquote class="content-quote">
<p>
<script type="math/tex">f=500MHz</script>
</p>
<p>
<script type="math/tex">T=\cfrac{1}{500*10^6}=2*10^{-9}s=2ns</script>
</p>
</blockquote>
<ul>
<li>
<p>设备A采用定时查询I/O方式的周期：<script type="math/tex">2*4*10=80ns</script>
</p>
</li>
<li>
<p>设备A准备32位数据所用的时间为：<script type="math/tex">32bit=4B</script>，<script type="math/tex">\cfrac{4B}{2MB/s}=2us</script>，所以必须<script type="math/tex">2us</script>查询一次。</p>
</li>
<li>
<p>CPU用于设备A输入/输出的时间占CPU总时间的百分比：<script type="math/tex">\cfrac{80ns}{2us}=\cfrac{80ns}{2000ns}=4\%</script>
</p>
</li>
</ul>
<h6 id="2io400bio">（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？</h6>
<ul>
<li>
<p>设备B能否采用中断I/O方式的周期：<script type="math/tex">2ns*400=800ns=0.8us</script>
</p>
</li>
<li>
<p>设备B准备32位数据所用的时间为：<script type="math/tex">32bit=4B</script>，<script type="math/tex">\cfrac{4B}{40MB/s}=0.1us</script>
</p>
</li>
<li>
<p>准备数据的时间小于中断响应和中断处理的时间，数据就会被刷新、造成丢失。设备B不能采用中断I/O方式。</p>
</li>
</ul>
<h6 id="3bdmadma1000bcpudma500cpubcpu">（3）若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输人/输出的时间占CPU总时间的百分比最多是多少？</h6>
<ul>
<li>
<p>CPU用于DMA预处理和后处理的总时钟周期：<script type="math/tex">2ns*500=1000ns=1us</script>
</p>
</li>
<li>
<p>设备A采用DMA方式的周期：<script type="math/tex">\cfrac{1000B}{40MB/s}=25us</script>
</p>
</li>
<li>
<p>CPU用于设备B输人/输出的时间占CPU总时间的百分比：<script type="math/tex">\cfrac{1us}{25us}=4\%</script>
</p>
</li>
</ul>
<h5 id="4415cpu4444">44、（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如。题44图所示。根据题44图回答下列问题。</h5>
<p><img class="pure-img" alt="3A01E725146BE536E8727AF86F1403FA" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/3A01E725146BE536E8727AF86F1403FA.jpg" /></p>
<h6 id="1_4">（1）主存物理地址占多少位？</h6>
<ul>
<li>物理地址：<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[实⻚号][⻚内地址]</code></span>：<script type="math/tex">(16+12)bit=28bit</script>
</li>
<li>或者，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[标记][组号][块内地址]</code></span>：<script type="math/tex">(20+3+5)bit=28bit</script>
</li>
</ul>
</li>
</ul>
<h6 id="2tlbtlbsramdram">（2）TLB采用什么映射方式？TLB用SRAM还是DRAM实现？</h6>
<ul>
<li>TLB采用全相联映射；</li>
<li>TLB用SRAM实现，写速度快，但成本高，多用于容量较小的高速缓冲存储器。</li>
</ul>
<h6 id="3cachecachelruwritebackcachedatatagcachecache">（3）Cache采用什么映射方式？若Cache采用LRU替换算法和回写（WriteBack）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？</h6>
<ul>
<li>Cache映射方式：Cache中每组有两行，故采用2路组相联映射方式。</li>
<li>LRU替换算法：将最久没有被访问过的主存块替换。</li>
<li>回写策略：CPU对Cache写命中时，只修改Cache中的内容，只有当此块被换出时才写回主存。</li>
<li>附加位：<ul>
<li>2路组相联并采用LRU替换算法，每行（或每组）需要1位LRU位；</li>
<li>采用回写策略，每行有1位修改位（脏位）；</li>
</ul>
</li>
<li>Cache总容量：<ul>
<li>物理地址组成：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[标记][组号][块内地址]</code></span>：<script type="math/tex">(20+3+5)bit=28bit</script>
</li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[组号]</code></span>：<script type="math/tex">3bit</script>，表示8组，每组2行，共16行。</li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[块内地址]</code></span>：<script type="math/tex">5bit</script>，表示<script type="math/tex">2^5=32</script>个地址，计算机按字节编址。（一个块的大小为<script type="math/tex">32B</script>）</li>
<li>Cache总容量：<script type="math/tex; mode=display">行数*(Tag+[LRU位]+[脏位]+有效位+一个块保存数据大小)</script>
</li>
<li>Cache总容量：<script type="math/tex; mode=display">16*(20+1+1+1+32*8)=4464bit=558B</script>
</li>
</ul>
</li>
</ul>
<h6 id="4cpu0008c040hcachecpu0007c260hcache">（4）若CPU给出的虚拟地址为0008C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由，若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache组号是多少？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0008C040]H</code></span></th>
<th></th>
<th></th>
<th></th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>虚拟地址</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[虚页号20]</code></span></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[⻚内地址12]</code></span></td>
<td></td>
</tr>
<tr>
<td>LTB格式</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag20]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[实⻚号16]</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>物理地址</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[实⻚号16]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[⻚内地址12]</code></span></td>
<td></td>
</tr>
<tr>
<td>Cache格式</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag16</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag4][组号3][块内地址5]</code></span></td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>虚拟地址</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0008C]H</code></span></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[040]H</code></span></td>
<td></td>
</tr>
<tr>
<td>LTB格式</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0008C]H</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[****]H</code></span></td>
<td></td>
<td>对应<span style="overflow-x: auto; max-width:100%; display:inline;"><code>实页号[0040]H</code></span>，LTB命中。</td>
</tr>
<tr>
<td>物理地址</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0040]H</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[040]H</code></span></td>
<td></td>
</tr>
<tr>
<td>Cache格式</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0040</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0]H[010]B[0 0000]B</code></span></td>
<td>Cache组号：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[010]B</code></span>。<br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag[00400]H</code></span>对应，有效位为0。<br /> <span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag[01600]H</code></span>不对应。<br />综上，Cache未命中。</td>
</tr>
</tbody>
</table></div>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0007C260]H</code></span></th>
<th></th>
<th></th>
<th></th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>虚拟地址</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[虚页号20]</code></span></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[⻚内地址12]</code></span></td>
<td></td>
</tr>
<tr>
<td>LTB格式</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag20]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[实⻚号16]</code></span></td>
<td></td>
<td></td>
</tr>
<tr>
<td>物理地址</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[实⻚号16]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[⻚内地址12]</code></span></td>
<td></td>
</tr>
<tr>
<td>Cache格式</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[Tag16</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Tag4][组号3][块内地址5]</code></span></td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>虚拟地址</td>
<td></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[260]H</code></span></td>
<td></td>
</tr>
<tr>
<td>Cache格式</td>
<td></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>2]H[011]B[0 0000]B</code></span></td>
<td>映射到的Cache组号：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[011]B</code></span></td>
</tr>
</tbody>
</table></div>
<h5 id="45844">45、（8分）请根据题44图给出的虚拟储管理方式，回答下列问题。</h5>
<p><img class="pure-img" alt="3A01E725146BE536E8727AF86F1403FA" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/3A01E725146BE536E8727AF86F1403FA.jpg" /></p>
<h6 id="1668">（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>页表</th>
<th></th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>虚拟地址</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[虚页号20]</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[⻚内地址12]</code></span></td>
</tr>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[页目录号10][页号10]</code></span></td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000 0001 10][00 0000 0110]B</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000 0000 1000]B</code></span></td>
</tr>
</tbody>
</table></div>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000 0001 10][00 0000 0110][0000 0000 1000]B</code></span> = <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0180 6008]H</code></span></p>
<h6 id="2pdbrpdbrpdbr">（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。</h6>
<ul>
<li>PDBR 为⻚目录基址地址寄存器( Page-Directory Base Register )<ul>
<li><strong>存储</strong>：⻚目录表物理内存基地址。</li>
<li><strong>进程切换</strong>时， PDBR 的内容会变化；每个进程的地址空间、⻚目录和 PDBR 的内容存在一一对应的关系。进程切换时，地址空间发生 了变化，对应的⻚目录及其起始地址也相应变化，因此需要用进程切换后当前进程的⻚目录起始地址刷新 PDBR 。</li>
<li><strong>同一进程的线程切换</strong>时， PDBR 的内容不会变化。 同一进程中的线程共享该进程的地址空间， 其线程发生切换时， 地址空间不变， 线程使用的⻚目录不变，因此 PDBR 的内容也不变。</li>
</ul>
</li>
</ul>
<h6 id="3clock">（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？</h6>
<ul>
<li>改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段(使用位)和 修改字段(脏位) 。</li>
</ul>
<h5 id="4674kb64b11814b">46、（7分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。</h5>
<h6 id="1_5">（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可）</h6>
<ul>
<li>簇大小：<script type="math/tex">4KB</script> 。</li>
<li>每个地址项⻓度为 <script type="math/tex">4B</script> ，故每簇有 <script type="math/tex">4KB / 4B = 1024</script> 个地址项。</li>
<li>最大文件的物理块数：<script type="math/tex; mode=display">(直接地址项数) + (一级 * 每簇项数)^1 + (二级 * 每簇项数^2) + (三级 * 每簇项数^3)</script>
</li>
<li>最大文件的物理块数：<script type="math/tex">8 + 1*1024^1 + 1*1024^2 + 1*1024^3</script>，每个物理块（簇）大小为 <script type="math/tex">4KB</script> 。</li>
<li>故最大文件⻓度： <script type="math/tex; mode=display">(8 + 1*1024^1 + 1*1024^2 + 1*1024^3)*4KB = 32KB + 4MB + 4GB + 4TB</script>
</li>
</ul>
<h6 id="21m1m-220512m5600b">（2）文件系统用1M（<script type="math/tex">1M = 2^{20}</script>）个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件？</h6>
<ul>
<li>用512M个簇存放文件数据计算：<ul>
<li>
<script type="math/tex">5600B = 5.6KB</script>
</li>
<li>
<script type="math/tex">5.6KB / 4KB = 2</script> 个簇</li>
<li>
<script type="math/tex">512M / 2 = 256M</script> 个文件</li>
</ul>
</li>
<li>用1M（<script type="math/tex">1M = 2^{20}</script>）个簇存放文件索引节点计算：<ul>
<li>每个文件索引节点占 <script type="math/tex">64B</script>
</li>
<li>
<script type="math/tex">\cfrac{1M * 4KB}{64B} = \cfrac{2^{12}MB}{2^6B} = 64M</script> 个文件</li>
</ul>
</li>
<li>综上，该文件系统最多能存放 <script type="math/tex">64M</script> 个这样的图像文件。</li>
</ul>
<h6 id="3f16kbf240kbf1f2">（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？</h6>
<ul>
<li>文件 F1 大小为 <script type="math/tex">6KB</script>， <script type="math/tex">6KB < 4KB * 8=32KB</script> ，故获取文件 F1 的最后一个簇的簇号只需要访问索引节点的直接地址项。</li>
<li>文件 F2 大小为 <script type="math/tex">40KB</script> ， <script type="math/tex">4KB * 8 < 40KB < 4KB * 8 + 4KB * 1 * 1024^1</script> ，故获取 F2 的 最后一个簇的簇号还需要读一级索引表。</li>
<li>综上，需要的时间不相同。</li>
</ul>
<h5 id="47747ip1921681024ipmtu1500bmtu800b">47、（7分）某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201216151043126.png" alt="image-20201216151043126" style="zoom:50%;" /></p>
<h6 id="1ip">（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？</h6>
<ul>
<li>销售部子网的广播地址：192.168.1.127</li>
<li>技术部子网的子网地址：192.168.1.128<ul>
<li>技术部子网的广播地址：192.168.1.255</li>
<li>总共地址数：<script type="math/tex">254-129+1 = 126</script>
</li>
<li>以分配地址数：<script type="math/tex">208-129+1 = 80</script>
</li>
<li>剩余可分配数量：<script type="math/tex">126-80=46</script>，<strong>错误</strong></li>
<li>注意：还有一个地址 192.168.1.254 分配给了路由器的端口F1</li>
<li><strong>最后，剩余可分配数量：<script type="math/tex">45</script></strong></li>
</ul>
</li>
</ul>
<h6 id="21921681119216812081500bipip20bf1ipip">（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？</h6>
<ul>
<li>判断分片的大小，需要考虑各个网段的 <script type="math/tex">MTU</script>，而且<u>注意分片的数据⻓度必须是 <script type="math/tex">8B</script> 的整数倍</u>。</li>
<li>
<script type="math/tex">F0</script>端口，<script type="math/tex">MTU=1500B</script>：<ul>
<li>
<script type="math/tex">1500B = (20 + 1480)B</script> ，其中 <script type="math/tex">1480 / 8 = 185</script>
</li>
</ul>
</li>
<li>
<script type="math/tex">F1</script>端口，<script type="math/tex">MTU=800B</script>：<ul>
<li>注意：<script type="math/tex">780 / 8 = 97.5</script>，不是<script type="math/tex">8B</script>的整数倍。</li>
<li>最大数据长度：<script type="math/tex">97*8=776B</script>
</li>
<li>结果，被分成 <script type="math/tex">(20 + 776)B + (20 + 724)B</script>
</li>
<li>因此：<ul>
<li>最大IP分片封装数据的字节数是 <script type="math/tex">776B</script>
</li>
<li>需要分为 <script type="math/tex">2</script> 个分片。</li>
<li>第1个分片的偏移量为 <script type="math/tex">0</script>
</li>
<li>第2个分片的偏移量为 <script type="math/tex">776/8=97</script>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h1 id="2017">2017真题</h1>
<h5 id="4115">41、（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201216153342994.png" alt="image-20201216153342994" style="zoom:50%;" /></p>
<p>输出的等价中缀表达式分别为<script type="math/tex">(a+b)*(c*(-d))和(a*b)+(-(c-d))</script>。二叉树结点定义如下：</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">typedef struct node
{
    char data[10]; //存储操作数或操作符
    struct node *left, *right;
} BTree;
</code></span></code></pre>
<p>要求：</p>
<h6 id="1_6">（1）给出算法的基本设计思想。</h6>
<ul>
<li>表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分) </li>
<li>表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。(2分)</li>
</ul>
<h6 id="2cc">（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</h6>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

typedef struct node
{
    char data[10];
    struct node *left, *right;
} BTree;

void SetData(BTree **root, const char data[])
{
    (*root) = (BTree *)malloc(sizeof(BTree));
    (*root)-&gt;data[0] = data[0];
    (*root)-&gt;data[1] = '\0';
    (*root)-&gt;left = NULL;
    (*root)-&gt;right = NULL;
}

/* 需要算法在此之间*/
void BtreeToExp(BTree * root, int deep)
{
    if (root == NULL) { 
        return;
    }
    else if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL) {
        printf(&quot;%s&quot;, root-&gt;data);
    }
    else {
        if (deep &gt; 1) printf(&quot;(&quot;);
        BtreeToExp(root-&gt;left, deep + 1); 
        printf(&quot;%s&quot;, root-&gt;data); 
        BtreeToExp(root-&gt;right, deep + 1);
        if (deep &gt; 1) printf(&quot;)&quot;);
    }
}

void BtreeToE(BTree *root) 
{
    BtreeToExp(root, 1); 
}
/* 需要算法在此之间*/

int main(int argc, char const *argv[])
{
    BTree *root;

    SetData(&amp;root, &quot;*&quot;);
    SetData(&amp;root-&gt;left, &quot;+&quot;);
    SetData(&amp;root-&gt;left-&gt;left,  &quot;a&quot;);
    SetData(&amp;root-&gt;left-&gt;right, &quot;b&quot;);

    SetData(&amp;root-&gt;right, &quot;*&quot;);
    SetData(&amp;root-&gt;right-&gt;left,  &quot;c&quot;);
    SetData(&amp;root-&gt;right-&gt;right, &quot;-&quot;);
    SetData(&amp;root-&gt;right-&gt;right-&gt;right, &quot;d&quot;);

    BtreeToE(root);
    printf(&quot;\n&quot;);

    BTree *root2;

    SetData(&amp;root2, &quot;+&quot;);
    SetData(&amp;root2-&gt;left, &quot;*&quot;);
    SetData(&amp;root2-&gt;left-&gt;left,  &quot;a&quot;);
    SetData(&amp;root2-&gt;left-&gt;right, &quot;b&quot;);

    SetData(&amp;root2-&gt;right, &quot;-&quot;);
    SetData(&amp;root2-&gt;right-&gt;right, &quot;-&quot;);
    SetData(&amp;root2-&gt;right-&gt;right-&gt;left,  &quot;c&quot;);
    SetData(&amp;root2-&gt;right-&gt;right-&gt;right, &quot;d&quot;);

    BtreeToE(root2);
    printf(&quot;\n&quot;);
    return 0;
}
</code></span></code></pre>
<h5 id="428primmst">42、（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。</h5>
<h6 id="1gagmst">（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201216153751651.png" alt="image-20201216153751651" style="zoom:50%;" /></p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>(A，D)，(D，E)，(C，E)，(B，C)</code></span></p>
<h6 id="2gmst">（2）图G的MST是唯一的吗？</h6>
<ul>
<li>图G的MST是唯一的。</li>
</ul>
<h6 id="3mst">（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？</h6>
<ul>
<li>当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。</li>
</ul>
<h5 id="4313fn-sum_i0n-2i-2n1-1fncf1">43、（13分）已知<script type="math/tex">f(n) = \sum_{i=0}^n 2^i = 2^{n+1}-1</script>，计算<script type="math/tex">f(n)</script>的C语言函数f1如下：</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">int f1(unsigned n)
{
    int sum = 1, power = 1;

    for (unsigned i = 0; i &lt;= n - 1; i++) {
        power *= 2;
        sum += power;
    }
    return sum;
}
</code></span></code></pre>
<p>将<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>中的int都改为float，可得到计算<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)</code></span>的另一个函数<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。请回答下列问题。</p>
<h6 id="1n0f1f1inintf1">（1）当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n=0</code></span>时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>会出现死循环，为什么？若将<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>中的变量i和n都定义为int型，则f1是否还会出现死循环？为什么？</h6>
<ul>
<li>由于i和n是unsigned型，故“i&lt;=n-1”是无符号数比较，n=0时，n-1的机器数为全1，值是232-1，为unsigned型可表示的最大数，条件“i&lt;=n-1”永真，因此出现死循环。(2分) 若i和n改为int类型，则不会出现死循环。(1分) 因为“i&lt;=n-1”是带符号整数比较，n=0时，n-1的值是-1，当i=0时条件“i&lt;=n-1”不成立，此时退出for循环。(1分)</li>
</ul>
<h6 id="2f123f223">（2）<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(23)</code></span>和<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(23)</code></span>的返回值是否相等？机器数各是什么（用十六进制表示）？</h6>
<ul>
<li>f1(23)与f2(23)的返回值相等。(1分)</li>
<li>f1(23)的机器数是00FF FFFFH，(1分)</li>
<li>f2(23)的机器数是4B7F FFFFH。(1分)</li>
</ul>
<h6 id="3f124f22433554431335544320">（3）<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(24)</code></span>和<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(24)</code></span>的返回值分别为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>33554431</code></span>和<span style="overflow-x: auto; max-width:100%; display:inline;"><code>33554432.0</code></span>，为什么不相等？</h6>
<ul>
<li>当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n=24</code></span>时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(24)=1 1111 1111 1111 1111 1111 1111 B</code></span>，而float型数只有24位有效位，舍入后数值增大，所以<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(24)</code></span>比<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(24)</code></span>大1。(1分)</li>
</ul>
<h6 id="4f31232-1f31-1f1nfnn">（4）<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(31)=2^{32}-1</code></span>，而<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(31)</code></span>的返回值却为-1，为什么？若使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(n)</code></span>的返回值与<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)</code></span>相等，则最大的n是多少？</h6>
<ul>
<li>显然<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(31)</code></span>已超出了int型数据的表示范围，用<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(31)</code></span>实现时得到的机器数为32个1，作为int型数解释时其值为-1，即f1(31)的返回值为-1。(1分)</li>
<li>因为int型最大可表示数是0后面加31个1，故使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(n)</code></span>的返回值与<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(n)</code></span>相等的最大n值是30。(1分)</li>
</ul>
<h6 id="5f21277f800000hf2nnf2nn">（5）<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(127)</code></span>的机器数为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>7F800000H</code></span>，对应的值是什么？若使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(n)</code></span>的结果不溢出，则最大的n是多少？若使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2(n)</code></span>的结果精确（无舍入），则最大的n是多少？</h6>
<ul>
<li>IEEE 754标准用“阶码全1、尾数全0”表示无穷大。<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>返回值为float型，机器数<span style="overflow-x: auto; max-width:100%; display:inline;"><code>7F80 0000H</code></span></li>
<li>对应的值是<script type="math/tex">+\infty</script>。(1分) 当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n=126</code></span>时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(126)=2^{217}-1=1.1...1×2^{126}</code></span>，对应阶码为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>127+126=253</code></span>，尾数部分舍入后阶码加1。</li>
<li>最终阶码为254，是IEEE754单精度格式表示的最大阶码。故使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>结果不溢出的最大n值为126。 (1分)</li>
<li>当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n=23</code></span>时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f(23)</code></span>为24位1，float型数有24位有效位，所以不需舍入，结果精确。故使<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>获得 精确结果的最大n值为23。 (1分)</li>
</ul>
<h5 id="4410m43f1">44、（10分）在按字节编址的计算机M上，题43中<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下：其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。</h5>
<p><img class="pure-img" alt="截屏2020-12-16 20.29.16" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 20.29.16.png" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">int f1(unsigned n)
{
    int sum = 1, power = 1;

    for (unsigned i = 0; i &lt;= n - 1; i++) {
        power *= 2;
        sum += power;
    }
    return sum;
}
</code></span></code></pre>
<h6 id="1mrisccisc">（1）计算机M是RISC还是CISC？为什么？</h6>
<ul>
<li>M为CISC。(1分)，M的指令长短不一，不符合RISC指令系统特点。(1分)</li>
</ul>
<h6 id="2f1">（2）<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>的机器指令代码共占多少字节？要求给出计算过程。</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0040107F H - 00401020 H + 1 H</code></span> = <span style="overflow-x: auto; max-width:100%; display:inline;"><code>7F - 20 H + 1 H = 5F + 1 H = 96 D</code></span></li>
<li>计算机M按字节编址，共96B。</li>
</ul>
<h6 id="320cmpin-1in-1f10i0cmpcf">（3）第20条指令cmp通过i减n-1实现对i和n-1的比较。执行<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(0)</code></span>过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么？要求给出计算过程。</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>cmp</code></span>指令实现<span style="overflow-x: auto; max-width:100%; display:inline;"><code>i</code></span>与<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n-1</code></span>的比较功能，进行的是减法运算。</li>
<li>在执行<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1(0)</code></span>过程中，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n=0</code></span>，当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=0</code></span>时， <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=0000 0000H</code></span>，并且<span style="overflow-x: auto; max-width:100%; display:inline;"><code>n-1=FFFF FFFFH</code></span>。</li>
<li>因此，当执行第20条指令时，在补码加/减运算器中执行 “0减FFFF FFFFH”的操作，即<span style="overflow-x: auto; max-width:100%; display:inline;"><code>0000 0000H+00000000H+1=0000 0001H</code></span>，此时，进位输出<span style="overflow-x: auto; max-width:100%; display:inline;"><code>C=0</code></span>，借位标志<span style="overflow-x: auto; max-width:100%; display:inline;"><code>F=1</code></span></li>
<li>减法运算时的借位标志<span style="overflow-x: auto; max-width:100%; display:inline;"><code>CF=C^1=1</code></span></li>
</ul>
<h6 id="423sh1power2f2sh1power2">（4）第23条指令<span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1</code></span>通过左移操作实现了<span style="overflow-x: auto; max-width:100%; display:inline;"><code>power*2</code></span>运算，在<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2​</code></span>中能否也用<span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1</code></span>指令实现<span style="overflow-x: auto; max-width:100%; display:inline;"><code>power*2</code></span>？为什么？</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>中不能用<span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1</code></span>指令实现<span style="overflow-x: auto; max-width:100%; display:inline;"><code>power*2</code></span>。(1分) </li>
<li>因为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1</code></span>指令用来将一个整数的所有有效数位作为一个整体左移；而<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>中的变量power是float型，其机器数中不包含最高有效数位，但包含了阶码部分，将其作为一个整体左移时并不能实 现“乘2”的功能，因而<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f2</code></span>中不能用<span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1</code></span>指令实现<span style="overflow-x: auto; max-width:100%; display:inline;"><code>power*2</code></span>。(2分)</li>
</ul>
<h5 id="45744m">45、（7分）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：</h5>
<p><img class="pure-img" alt="截屏2020-12-16 20.45.35" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 20.45.35.png" /></p>
<p>请针对题43的函数f1和题44中的机器指令代码，回答下列问题。</p>
<h6 id="1f1">（1）函数f1的机器指令代码占多少页？</h6>
<ul>
<li>一页的容量为<script type="math/tex">2^{12}=4KB</script>
</li>
<li>函数<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>的代码段的大小为<script type="math/tex">96B</script>，但是本题中应该看指令虚拟地址的高20位是否相同。</li>
<li>函数<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>的代码段中所有指令的虚拟地址的高20位相同，因此f1的机器指令代码在同一页中，仅占用1页。(1分)</li>
</ul>
<h6 id="21push-ebp0">（2）取第1条指令（<span style="overflow-x: auto; max-width:100%; display:inline;"><code>push ebp</code></span>）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）？</h6>
<ul>
<li>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>00401020 H =</code></span></p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000 0000 01][00 0000 0001][0000 0010 0000]B</code></span></p>
</li>
<li>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>push ebp</code></span>指令的虚拟地址的最高10位(页目录号)为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>00 00000001</code></span>，中间10位(页表索引)为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>00 0000 0001</code></span>，所以，取该指令时访问了页目录的第1个表项，(1分)在对应的页表中访问了第1个表项。(1分)</p>
</li>
</ul>
<h6 id="3miopf1scanfnscanfpcpu">（3）M的I/O采用中断控制方式。若进程P在调用<span style="overflow-x: auto; max-width:100%; display:inline;"><code>f1</code></span>之前通过<span style="overflow-x: auto; max-width:100%; display:inline;"><code>scanf()</code></span>获取n的值，则在执行<span style="overflow-x: auto; max-width:100%; display:inline;"><code>scanf()</code></span>的过程中，进程P的状态会如何变化？CPU是否会进入内核态？</h6>
<ul>
<li>在执行<span style="overflow-x: auto; max-width:100%; display:inline;"><code>scanf( )</code></span>的过程中，进程P因等待输入而从执行态变为阻塞态。(1分)</li>
<li>输入结束时，P 被中断处理程序唤醒，变为就绪态。(1分)</li>
<li>P被调度程序调度，变为运行态。(1分)</li>
<li>CPU状态会从 用户态变为内核态。(1分)</li>
</ul>
<h5 id="4683thread1thread2thread3pvwaitsignal">46、（8分）某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。请添加必要的信号量和P、V（或<span style="overflow-x: auto; max-width:100%; display:inline;"><code>wait()</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>signal()</code></span>）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201216205301073.png" alt="image-20201216205301073" style="zoom:67%;" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>semaphore mutex_y1 = 1; //mutex_y1用于thread1与thread3对变量y的互斥访问。(1分) 
semaphore mutex_y2 = 1; //mutex_y2用于thread2与thread3对变量y的互斥访问。(1分) 
semaphore mutex_z  = 1; //mutex_z用于变量z的互斥访问。(1分)
</code></span></code></pre>
<p>互斥代码如下：(5分)</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 20.55.59.png" alt="截屏2020-12-16 20.55.59" style="zoom:67%;" /></p>
<ul>
<li>thread1和thread2对y并不需要互斥。</li>
<li>只需要对读写进行互斥访问。</li>
</ul>
<h5 id="479ngbn1000bsxyrxyxy3100mbpsrtt096mst00t1">47、（9分）甲乙双方均采用后退N帧协议（GBN）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。Sx，y和Rx，y分别表示甲方和乙方发送的数据帧，其中：x是发送序号；y是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=0.96ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中t0为初始时刻，此时甲方的发送和确认序号均为0，t1时刻甲方有足够多的数据待发送。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-16 21.02.15.png" alt="截屏2020-12-16 21.02.15" style="zoom:50%;" /></p>
<h6 id="1at0t1sxy">（1）对于图(a)，t0时刻到t1时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧（请用Sx，y形式给出）？</h6>
<ul>
<li>可以判断乙方正确接收：<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S0,0</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S1,0</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S2,0</code></span></li>
<li>共3个数据帧</li>
</ul>
</li>
</ul>
<h6 id="2at1sxy">（2）对于图(a)，从t1时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个（请用Sx，y形式给出）？</h6>
<p><strong>自动重传请求（ARQ）</strong>  </p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>后退N帧</th>
</tr>
</thead>
<tbody>
<tr>
<td>描述</td>
<td>发送方连续发送N帧，如果接收方某个帧出错了，<br />接收方就丢弃所有帧，发送方没有等到确认帧，就超时重发所有帧。</td>
</tr>
<tr>
<td>发送窗口</td>
<td>
<script type="math/tex">1 < W_t < 2^n - 1</script>
</td>
</tr>
<tr>
<td>接收窗口</td>
<td>
<script type="math/tex">1</script>
</td>
</tr>
</tbody>
</table></div>
<ul>
<li>由于，数据帧的发送序号和确认序号字段均为3比特。</li>
<li>发送窗口的大小为7</li>
<li>接收窗口的大小为1</li>
<li>当前已经发送了<span style="overflow-x: auto; max-width:100%; display:inline;"><code>0 1 2 3 4</code></span>号帧，确认了<span style="overflow-x: auto; max-width:100%; display:inline;"><code>0 1 2</code></span>号帧</li>
<li>
<p>
<script type="math/tex">0\ 1\ 2\ [\underline{\ 3\ 4}\ 5\ 6\ 7\ 0\ 1\ ]\ 2\ 3\ 4\ 5\ 6</script>
</p>
</li>
<li>
<p>因此，从t1时刻起，甲方最多还可以发送5个数据帧(1分)</p>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S5,2</code></span>，第一个帧(1分)</li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S6,2</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S7,2</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S0,2</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S1,2</code></span>，最后一个帧(1分)</li>
</ul>
</li>
</ul>
<h6 id="3bt1sxy">（3）对于图(b)，从t1时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个（请用Sx，y形式给出）？</h6>
<ul>
<li>甲方需要重发3个数据帧。(1分)</li>
<li>重发的第一个帧是<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S2,3</code></span>。(1分)</li>
<li>补充：重发的帧为：<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S2,3</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S3,3</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S4,3</code></span></li>
</ul>
</li>
</ul>
<h6 id="4_1">（4）甲方可以达到的最大信道利用率是多少？</h6>
<p>
<script type="math/tex; mode=display">
\begin{equation}\begin{split} 
最大信道利用率 
&= \cfrac{一帧数据的发送时延 * 窗口大小}{一帧数据的发送时延 + 确认帧的发送时延 + 往返时延} = \cfrac{t*n}{t +  a + RTT} \\
&= \cfrac{\cfrac{1000\ B}{100\ Mbps}*7}{\cfrac{1000\ B}{100\ Mbps} + \cfrac{1000\ B}{100\ Mbps} + 0.96\ ms} 
= \cfrac{0.08*7}{0.08 + 0.08 +0.96} 
= 50\%
\end{split}\end{equation}
</script>
</p>
<h1 id="2016">2016真题</h1>
<h5 id="419334lh3websstcp20kbk1024mss1kbrtt200msh3100msss32kbstcpstcp">41、（9分）假设题33~4l图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。请回答下列问题。</h5>
<p><img class="pure-img" alt="image-20201220201219673" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201220201219673.png" /></p>
<h6 id="1tcph3stcpsynack">（1）在TCP连接建立过程中，H3收到的S发送过来的第二次握手TCP段的SYN和ACK标志位的值分别是多少？确认序号是多少？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>三次握手</th>
<th></th>
<th></th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>第一次握手</td>
<td>客服端</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>&gt;&gt;&gt;&gt;&gt;  SYN=1，     ，seq=x  ，         &gt;&gt;&gt;&gt;&gt;</code></span></td>
<td>服务端</td>
</tr>
<tr>
<td>第二次握手</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>&lt;&lt;&lt;&lt;&lt;  SYN=1，ACK=1，seq=y  ，ack=x+1  &lt;&lt;&lt;&lt;&lt;</code></span></td>
<td></td>
</tr>
<tr>
<td>第三次握手</td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>&gt;&gt;&gt;&gt;&gt;       ，ACK=1，seq=x+1，ack=y+1  &gt;&gt;&gt;&gt;&gt;</code></span></td>
<td></td>
</tr>
</tbody>
</table></div>
<p>第二次握手TCP段的SYN和ACK标志位的值分别是：1和1</p>
<p>确认序号是：101</p>
<h6 id="2h38h3h3">（2）H3收到的第8个确认段所通告的接收窗口是多少？此时H3的拥塞窗口变为多少？H3的发送窗口变为多少？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>RTT</th>
<th>总发送通告段</th>
<th>发送通告段序号</th>
<th>S的接收窗口</th>
<th>H3的拥塞窗口</th>
<th>H3的发送窗口</th>
</tr>
</thead>
<tbody>
<tr>
<td>INIT</td>
<td></td>
<td></td>
<td>20</td>
<td>MSS=1KB</td>
<td>1</td>
</tr>
<tr>
<td>第1个RTT结束</td>
<td>共1个通告段</td>
<td>第1个</td>
<td>19</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>第2个RTT结束</td>
<td>共2个通告段</td>
<td>第2到3个</td>
<td>17</td>
<td>4</td>
<td>4</td>
</tr>
<tr>
<td>第3个RTT结束</td>
<td>共4个通告段</td>
<td>第4到7个</td>
<td>13</td>
<td>8</td>
<td>8</td>
</tr>
</tbody>
</table></div>
<p>第四个RTT<strong>开始</strong>：</p>
<p>第8个通告段，S的接收窗口 <script type="math/tex">12KB</script>，此时H3的拥塞窗口 <script type="math/tex">9KB</script>，H3的发送窗口 <script type="math/tex">\min\{12, 9\}KB=9KB</script>
</p>
<h6 id="3h30h310">（3）当H3的发送窗口等于0时，下一个待发送的数据段序号是多少？H3从发送第1个数据段到发送窗口等于0时刻为止，平均数据传输速率是多少（忽略段的传输延时）？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>RTT</th>
<th>总发送通告段</th>
<th>发送通告段序号</th>
<th>S的接收窗口</th>
<th>H3的拥塞窗口</th>
<th>H3的发送窗口</th>
</tr>
</thead>
<tbody>
<tr>
<td>第4个RTT结束</td>
<td>共8个通告段</td>
<td>第8到15个通告段</td>
<td>5</td>
<td>16</td>
<td>5</td>
</tr>
<tr>
<td>第5个RTT结束</td>
<td>共16个通告段</td>
<td>第16个通告段</td>
<td>4</td>
<td>17</td>
<td>4</td>
</tr>
<tr>
<td></td>
<td></td>
<td>第17个通告段</td>
<td>3</td>
<td>18</td>
<td>3</td>
</tr>
<tr>
<td></td>
<td></td>
<td>第18个通告段</td>
<td>2</td>
<td>19</td>
<td>2</td>
</tr>
<tr>
<td></td>
<td></td>
<td>第19个通告段</td>
<td>1</td>
<td>20</td>
<td>1</td>
</tr>
<tr>
<td></td>
<td></td>
<td>第20个通告段</td>
<td>0</td>
<td>21</td>
<td>0</td>
</tr>
</tbody>
</table></div>
<p>下一个待发送的数据段序号：<script type="math/tex">20*1024+100+1=20581</script>
</p>
<p>H3从发送第1个数据段到发送窗口等于0时刻为止，平均数据传输速率：<script type="math/tex">\cfrac{20*1024B}{5*200ms}=20480B/s=20.48KB/s</script>
</p>
<h6 id="4h3sth3ts">（4）若H3与S之间通信已经结束，在t时刻H3请求断开该连接，则从t时刻起，S释放该连接的最短时间是多少？</h6>
<p>在t时刻H3请求断开该连接，则从t时刻起，S释放该连接所需的最短时间为1个往返时延RTT加1个端到端传播时延（也就是RTT的一半），共1.5个RTT，即 <script type="math/tex">1.5×200ms=300ms</script>。</p>
<h5 id="428kk2tktk">42、（8分）如果一棵非空k（k≥2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。</h5>
<h6 id="1tmt">（1）若T有m个非叶结点，则T中的叶结点有多少个？</h6>
<h6 id="2thh1t">（2）若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？</h6>
<h5 id="4315nn2aak0kna1a2n1n2a1a2s1s2n1-n2s1-s2">43、（15分）已知由n（n≥2）个正整数构成的集合A={ak}0≤k&lt;n}，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：</h5>
<h6 id="1_7">（1）给出算法的基本设计思想。</h6>
<h6 id="2cc_1">（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</h6>
<h6 id="3_1">（3）说明你所设计算法的平均时间复杂度和空间复杂度。</h6>
<h5 id="449cpu50mhzcpi4d7ascii11dio05ms">44、（9分）假定CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，<u>从D接收启动命令到字符送入I/O端口需要0.5ms</u>。请回答下列问题，要求说明理由。</h5>
<h6 id="1di0">（1）每传送一个字符，在异步串行通信线上共需传输多少位？在设备D持续工作过程中，每秒钟最多可向I/0端口送入多少个字符？</h6>
<p>每传送一个ASCII字符，需要传输的位数有1位起始位、7位数据位(ASCII字符占7位)、1位奇校验位和1位停止位，故总位数为 <script type="math/tex">1+7+1+1=10</script>。(2分)</p>
<p>I/O端口每秒钟最多可接收 <script type="math/tex">1000/0.5=2000</script> 个字符。(1分)</p>
<h6 id="2dio102015dcpud1000cpucpu">（2）设备D采用中断方式进行输入/输出，示意图如下：I/O端口每收到一个字符申请一次中断，中断响应需10个时钟周期，中断服务程序共有20条指令，其中第15条指令启动D工作。若CPU需从D读取1000个字符，则完成这一任务所需时间大约是多少个时钟周期？CPU用于完成这一任务的时间大约是多少个时钟周期？在中断响应阶段CPU进行了哪些操作？</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-20 22.29.59.png" alt="截屏2020-12-20 22.29.59" style="zoom: 67%;" /></p>
<p>时钟周期：<script type="math/tex">\cfrac{1}{50 MHz}=0.02\mu s</script>
</p>
<p>一个字符传送时间包括：设备D将字符送I/0端口的时间、中断响应时间和中断服务程序。</p>
<p>前15条指令的执行时间。设备D将字符送I/0端口的时间为 <script type="math/tex">\cfrac{0.5 ms}{0.02\mu s}=2.5×10^4</script> 个时钟周期。</p>
<p>一个字符的传送时间大约为：<script type="math/tex">2.5×10^4+10+15×4=25070</script> 个时钟周期。</p>
<p>完成1000个字符传送所需时间大约为：<script type="math/tex">1000×25070=25070000</script> 个时钟周期。(3分)</p>
<p>CPU用于该任务的时间大约为：<script type="math/tex">1000×(10+20×4)=9×104</script> 个时钟周期。(1分)</p>
<p>在中断响应阶段，CPU主要进行以下操作：关中断、保护断点和程序状态、识别中断源。 (2分)</p>
<blockquote class="content-quote">
<p>区分：</p>
<p>CPU进行了哪些操作？（中断隐指令，硬件）</p>
<p>中断服务程序执行哪些操作？</p>
</blockquote>
<h5 id="451432248kbtlbcache64kb264b">45、（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/image-20201220222938632.png" alt="image-20201220222938632" style="zoom: 67%;" /></p>
<blockquote class="content-quote">
<p>参考：</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/3A01E725146BE536E8727AF86F1403FA.jpg" alt="3A01E725146BE536E8727AF86F1403FA" style="zoom: 67%;" /></p>
</blockquote>
<h6 id="1agtlbb">（1）图中字段A~G的位数各是多少？TLB标记字段B中存放的是什么信息？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>题目信息</th>
<th>字段A~G</th>
</tr>
</thead>
<tbody>
<tr>
<td>页大小为 <script type="math/tex">8KB=2^3+2^{10}=2^{13}B</script>，页内偏移地址为 <script type="math/tex">13bit</script>
</td>
<td>
<script type="math/tex">D=13</script>
</td>
</tr>
<tr>
<td>物理地址为 <script type="math/tex">24bit</script>
</td>
<td>
<script type="math/tex">C=24-13=11</script>
</td>
</tr>
<tr>
<td>虚拟地址为 <script type="math/tex">32bit</script>
</td>
<td>
<script type="math/tex">A=32-13=19</script><br /><script type="math/tex">B=A=19</script>
</td>
</tr>
<tr>
<td>Cache主存块大小为 <script type="math/tex">64B=2^6B</script>
</td>
<td>
<script type="math/tex">G=6</script>
</td>
</tr>
<tr>
<td>Cache数据区大小为 <script type="math/tex">64KB</script>，按2路组相联方式组织，每组数据区容量有 <script type="math/tex">64 B×2=128 B</script>
</td>
<td></td>
</tr>
<tr>
<td>Cache组数 <script type="math/tex">\cfrac{64KB}{128B}=512=2^9</script>
</td>
<td>
<script type="math/tex">F=9</script>
</td>
</tr>
<tr>
<td>物理地址为 <script type="math/tex">24bit</script>
</td>
<td>
<script type="math/tex">E=24-F-G=9</script>
</td>
</tr>
</tbody>
</table></div>
<p>TLB中标记字段B的内容是虚页号，表示该TLB项对应哪个虚页的页表项。(1分)</p>
<h6 id="24099cachecacheh">（2）将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少？对应的H字段内容是什么？</h6>
<blockquote class="content-quote">
<p>因为G = 6（Cache主存块大小为64B），块号为4099，意味着物理地址(24bit)的高 9+9 位为4099。</p>
</blockquote>
<p>块号 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>4099 = [0000 0100 0][000 0000 11][00 0000]B</code></span>，因此，所映射的Cache组号为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[000 0000 11]B = 3</code></span>（1分）</p>
<p>对应的H字段内容为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000 0100 0]B</code></span>（1分）</p>
<h6 id="3cache">（3）Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？</h6>
<p>Cache缺失带来的开销小，而处理缺页的开销大。(1分)</p>
<p>因为缺页处理需要访问磁盘，而Cache缺失只要访问主存。(1分)</p>
<h6 id="4cachewritethroughwriteback">（4）为什么Cache可以采用直写（WriteThrough）策略，而修改页面内容时总是采用回写（WriteBack）策略？</h6>
<p>因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多，所以，</p>
<p>在 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>Cache-主存</code></span> 层次，Cache可以采用直写策略，</p>
<p>而在 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>主存-外存(磁盘)</code></span> 层次，修改页面内容时总是采用回写策略。(2分)</p>
<h5 id="466prioritynicecputimewaittime0cputime1waittime0cputime0waittime1">46、（6分）某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。</h5>
<h6 id="1-nice-prioritynice">（1）若调度程序只将 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nice</code></span> 的值作为进程的优先数，即 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>priority=nice</code></span> ，则可能会出现饥饿现象，为什么？</h6>
<p>由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。(2分)</p>
<h6 id="2nicecputimewaittimewaittime">（2）使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。</h6>
<blockquote class="content-quote">
<p>选择优先数最小的进程运行.</p>
</blockquote>
<p>
<script type="math/tex">priority = nice + k1 × cpuTime - k2 × waitTime</script>
</p>
<p>其中 <script type="math/tex">k1>0</script>，<script type="math/tex">k2>0</script>，用来分别调整 cpuTime 和 waitTime 在priority中所占的比例。(3分)</p>
<p>waitTime 可使长时间等待的进程优先数减小，从而避免出现饥饿现象。(1分)</p>
<h5 id="4794kbfat">47、（9分）某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。</h5>
<h6 id="1dirdir1file1file2">（1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-20 22.29.04.png" alt="截屏2020-12-20 22.29.04" style="zoom: 50%;" /></p>
<p>两个目录文件dir和dir1的内容如下表所示。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-20 22.33.39.png" alt="截屏2020-12-20 22.33.39" style="zoom: 50%;" /></p>
<h6 id="2fat2fat">（2）若FAT的每个表项仅存放簇号，占2个字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？</h6>
<ul>
<li>由于FAT的簇号为2个字节，即16比特，因此在FAT表中最多允许 <script type="math/tex">2^{16}</script>（65536）个表项，一个FAT文件最多包含 <script type="math/tex">2^{16}</script>（65536）个簇。</li>
<li>FAT的最大长度为 <script type="math/tex">2^{16}×2 B=128 KB</script>。(1分)</li>
<li>文件的最大长度是 <script type="math/tex">2^{16}×4 KB=256 MB</script>。(1分)</li>
</ul>
<h6 id="3fatfile1106108fat">（3）系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。</h6>
<ul>
<li>在FAT的每个表项中存放下一个簇号。</li>
<li>file1的簇号106存放在FAT的100号表项中，(1分)</li>
<li>簇号108存放在FAT的106号表项中。(1分)</li>
</ul>
<h6 id="4fatdirdirdir1file15000">（4）假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？</h6>
<ul>
<li>先在dir目录文件里找到dir1的簇号，然后读取48号簇，得到dir1目录文件，接着找到file1的第一个簇号，据此在FAT里查找file1的第5000个字节所在的簇号，最后访问磁盘中的该簇。</li>
<li>需要访问目录文件dir1所在的48号簇，(1分)</li>
<li>及文件file1的106号簇。(1分)</li>
</ul>
<h1 id="2015">2015真题</h1>
<h5 id="4115mdataheadhead">41、（15分）用单链表保存m个整数，结点的结构为：时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如下：则删除结点后的head为：要习之：</h5>
<h6 id="1_8">（1）给出算法的基本设计思想。</h6>
<h6 id="2cc_2">（2）使用C或C++语言，给出单链表结点的数据类型定义。</h6>
<h6 id="3cc">（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</h6>
<h6 id="4_2">（4）说明你所设计算法的时间复杂度和空间复杂度。</h6>
<h5 id="4285g">42、（8分）已知含有5个顶点的图G如下图所示。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 08.30.15.png" alt="截屏2020-12-21 08.30.15" style="zoom:50%;" /></p>
<h6 id="1ga0">（1）写出图G的邻接矩阵A（行、列下标均从0开始）。</h6>
<p>
<script type="math/tex; mode=display">
A = \left[\begin{array}{c | c c c c} 
  & 0 & 1 & 2 & 3 & 4 \\
\hline
0 & 0 & 1 & 1 & 0 & 1\\
1 & 1 & 0 & 0 & 1 & 1\\
2 & 1 & 0 & 0 & 1 & 0\\
3 & 0 & 1 & 1 & 0 & 1\\
4 & 1 & 1 & 0 & 1 & 0
\end{array}\right]
</script>
</p>
<h6 id="2a2a203">（2）求<script type="math/tex">A^2</script>，矩阵<script type="math/tex">A^2</script>中位于0行3列元素值的含义是什么？</h6>
<p>
<script type="math/tex; mode=display">
A^2 = \left[\begin{array}{c | c c c c} 
  & 0 & 1 & 2 & 3 & 4 \\
\hline
0 & 3 & 1 & 0 & 3 & 1\\
1 & 1 & 3 & 2 & 1 & 2\\
2 & 0 & 2 & 2 & 0 & 2\\
3 & 3 & 1 & 0 & 3 & 1\\
4 & 1 & 2 & 2 & 1 & 3
\end{array}\right]
</script>
</p>
<ul>
<li>0行3列的元素值3表示从顶点0到顶点3之间长度为2的路径共有3条。</li>
</ul>
<h6 id="3nn2bbm2mn">（3）若已知具有n（n≥2）个顶点的图的邻接矩阵为B，则<script type="math/tex">B^m</script>（2≤m≤n）中非零元素的含义是什么？</h6>
<ul>
<li>
<script type="math/tex">B^m (2≤m≤n)</script> 中位于 <script type="math/tex">i</script> 行 <script type="math/tex">j</script> 列 <script type="math/tex">(0≤i，j≤n-1)</script> 的非零元素的含义是：图中从顶点 <script type="math/tex">i</script> 到顶点 <script type="math/tex">j</script> 长度为 <script type="math/tex">m</script> 的路径条数。</li>
</ul>
<h5 id="4313161616cpur0r3tsrmovleftright3sropsrsroutaluamovaabaddabsubabandaboranotaline7aluop">43、（13分）某16位计算机的主存按字节编址，存取单位为16位；采用16位定长指令字格式；CPU采用单总线结构，主要部分如下图所示。图中R0~R3为通用寄存器；T为暂存器；SR为移位寄存器，可实现直送（mov）、左移一位（left）和右移一位（right）3种操作，控制信号为SRop，SR的输出由信号SRout控制；ALU可实现直送A（mova）、A加B（add）、A减B（sub）、A与B（and）、A或B（or）、非A（not）、A加l（ine）7种操作，控制信号为ALUop。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 08.41.43.png" alt="截屏2020-12-21 08.41.43" style="zoom:50%;" /></p>
<h6 id="1t">（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T？</h6>
<ul>
<li><u>程序员可见寄存器为通用寄存器 (R0~R3) 和 PC。</u></li>
<li>因为采用了单总线结构，因此，若无暂存器T，则ALU的A、B端口会同时获得两个相同的数据，使数据通路不能正常工作。</li>
</ul>
<h6 id="2aluopsrop">（2）控制信号ALUop和SRop的位数至少各是多少？</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>寄存器</th>
<th>信号</th>
<th>操作</th>
<th>数量</th>
<th>位数</th>
</tr>
</thead>
<tbody>
<tr>
<td>ALU</td>
<td>ALUop</td>
<td>A(mova), A加B(add), A减B(sub), A与B(and), A或B(or), 非A(not), A加l(ine）</td>
<td>7种</td>
<td>3</td>
</tr>
<tr>
<td>SR</td>
<td>SRop</td>
<td>直送(mov), 左移一位(left)和右移一位(right)</td>
<td>3种</td>
<td>2</td>
</tr>
</tbody>
</table></div>
<h6 id="3srout">（3）控制信号SRout所控制部件的名称或作用是什么？</h6>
<ul>
<li>信号SRout所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。</li>
</ul>
<h6 id="41-9">（4）端点1-9中，哪些端点须连接到控制部件的输出端？</h6>
<ul>
<li>端口1、2、3、5、8须连接到控制部件输出端。</li>
</ul>
<h6 id="51-9">（5）为完善单总线数据通路，需要在端点1-9中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。</h6>
<ul>
<li>连线1，6→9；</li>
<li>连线2，7→4。</li>
</ul>
<h6 id="6mux2">（6）为什么二路选择器MUX的一个输入端是2？</h6>
<blockquote class="content-quote">
<p>MUX：（数据选择器(multiplexer)）</p>
</blockquote>
<ul>
<li>因为每条指令的长度为16位，按字节编址，所以每条指令占用2个内存单元，顺序执行时，下条指令地址为(PC)+2。MUX的一个输入端为2，可便于执行(PC)+2操作。</li>
</ul>
<h5 id="44104344a44a44b01r0r30123">44、（10分）<u>题43中描述的计算机</u>，其部分指令执行过程的控制信号如题44图a所示。题44图a部分指令的控制信号。该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0~R3的编号分别为0、1、2和3。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 08.42.02.png" alt="截屏2020-12-21 08.42.02" style="zoom: 67%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 08.43.47.png" alt="截屏2020-12-21 08.43.47" style="zoom:67%;" /></p>
<h6 id="1_9">（1）该机的指令系统最多可定义多少条指令？</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Md,Ms1,Ms2</code></span> 各占1位，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>Rd,Rs1,Rs2</code></span> 用于表示寄存器编号，需要 2 位，总共 <script type="math/tex">3(1+2)=9</script> 位。</li>
<li>按指令字长 16 位计算，指令操作码有 7 位，因此最多可定义 <script type="math/tex">2^7=128</script> 条指令。</li>
</ul>
<h6 id="2incshlsub01h02h03h">（2）假定inc、shl和sub指令的操作码分别为01H、02H和03H，则以下指令对应的机器代码各是什么？</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 09.41.30.png" alt="截屏2020-12-21 09.41.30" style="zoom:50%;" /></p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>指令</th>
<th>操作码（7bit）</th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Md</code></span></th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Rd</code></span></th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Ms1</code></span></th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Rs1</code></span></th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Ms2</code></span></th>
<th><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Rs2</code></span></th>
<th>机器代码</th>
</tr>
</thead>
<tbody>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>inc R1</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>01H = [0000001]B</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>01</code></span></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000001][001][000][000]B = 0280 H</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>sh1 R2,R1</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>02H = [0000010]B</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>10</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>01</code></span></td>
<td></td>
<td></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000010][010][001][000]B = 0488 H</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>sub R3,(R1),R2</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>03H = [0000011]B</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>11</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>1</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>01</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>10</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0000011][011][101][010]B = 06EA H</code></span></td>
</tr>
</tbody>
</table></div>
<h6 id="3xxinxout10pcout1pcmemopreadwrite44a18">（3）假设寄存器x的输入和输出控制信号分别记为Xin和Xout，其值为1表示有效，为0表示无效（例如，PCout=1表示PC内容送总线）；存储器控制信号为MEMop，用于控制存储器的读（read）和写（write）操作。写出题44图a中标号1~8处的控制信号或控制信号取值。</h6>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>标号</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 08.42.02.png" alt="截屏2020-12-21 08.42.02" style="zoom: 67%;" /></td>
</tr>
<tr>
<td>1</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>MUXop=0</code></span></td>
</tr>
<tr>
<td>2</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>SRop=mov</code></span></td>
</tr>
<tr>
<td>3</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>ALUop=mova</code></span></td>
</tr>
<tr>
<td>4</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>SRop=left</code></span></td>
</tr>
<tr>
<td>5</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>MEMop=read</code></span></td>
</tr>
<tr>
<td>6</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>ALUop=sub</code></span></td>
</tr>
<tr>
<td>7</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>SRop=mov</code></span></td>
</tr>
<tr>
<td>8</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>SRout=1</code></span></td>
</tr>
</tbody>
</table></div>
<h6 id="4sub-r1r3r2inc-r1">（4）指令“sub  R1，R3，（R2）”和“inc  R1”的执行阶段至少各需要多少个时钟周期？</h6>
<ul>
<li>sub  R1，R3，（R2）的执行阶段至少包含4个时钟周期;</li>
<li>inc  R1 的执行阶段至少包含2个时钟周期。</li>
</ul>
<h5 id="459abambnax0xmby0yn1abpvwaitsignal">45、（9分）有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放人对方的信箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0&lt;x&lt;M），B的信箱中有y个邮件（0&lt;y&lt;N）。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或wait、signal）操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 09.34.55.png" alt="截屏2020-12-21 09.34.55" style="zoom: 50%;" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>semaphore Full_A  = x ;     // Fuu_A表示A的信箱中的邮件数量
semaphore Empty_A = M-x ;   // Empty_A表示A的信箱中还可存放的邮件数量

semaphore Full_B  = y ;     // Full_B表示B的信箱中的邮件数量
semaphore Empty_B = N-y ;   // Empty_B表示B的信箱中还可存放的邮件数量

semaphore mutex_A = 1 ;     // mutex_A用于A的信箱互斥
semaphore mutex_B = 1 ;     // mutex_B用于B的信箱互斥

A{
    while(TRUE){
        P(Full_A);
        P(mutex_A);
        从 A 的信箱中取出一个邮件; 
        V(mutex_A);
        V(Empty_A);

        回答问题并提出一个新问题; 

        P(Empty_B);
        P(mutex_B);
        将新邮件放入 B 的信箱; 
        V(mutex_B);
        V(Full_B);
    }
}

B{
    while(TRUE){
        P(Full_B); 
        P(mutex_B);
        从 B 的信箱中取出一 个邮件; 
        V(mutex_B); 
        V(Empty_B); 

        回答问题并提出一个 新问题; 

        P(Empty_A); 
        P(mutex_A); 
        将新邮件放入 A 的 信箱; 
        V(mutex_A); 
        V(Full_A);
    }
}
</code></span></code></pre>
<h5 id="466">46、（6分）某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 09.35.21.png" alt="截屏2020-12-21 09.35.21" style="zoom:67%;" /></p>
<h6 id="1_10">（1）页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？</h6>
<blockquote class="content-quote">
<p>分页存储管理</p>
<p>将作业的 <strong>逻辑地址</strong> 划分为一系列同等大小的部分，称为页。</p>
<p>把可用的 <strong>物理内存</strong> 也划分为同样大小的连续的部分，称为块或页框。</p>
</blockquote>
<ul>
<li>页和页框大小均为 <script type="math/tex">2^{12}=4KB</script>。进程的虚拟地址空间大小为<script type="math/tex">\cfrac{2^{32}}{2^{12}} = 2^{20}</script>页。</li>
</ul>
<h6 id="24">（2）假定页目录项和页表项均占4个字节，则进程的页目录和页表共占多少页？要求写出计算过程。</h6>
<ul>
<li>
<script type="math/tex">\cfrac{2^{10}*4}{2^{12}}</script>（页目录所占页数）+ <script type="math/tex">\cfrac{2^{20}*4}{2^{12}}</script>（页表所占页数）= <script type="math/tex">1025</script> 页。</li>
</ul>
<h6 id="301000000h01112048h">（3）若某指令周期内访问的虚拟地址为01000000H和01112048H，则进行地址转换时共访问多少个二级页表？要求说明坪由。</h6>
<ul>
<li>需要访问一个二级页表。因为虚拟地址0100 0000H和0111 2048H的最高10位的值都是4，访问的是同一个二级页表。</li>
</ul>
<h5 id="47947dhcpwww1ip2ndhcpip">47、（9分）某网络拓扑如题47图所示，其中路由器内网接口、DHCP服务器、WWW服务器与主机1均采用静态IP地址配置，相关地址信息见图中标注；主机2~主机N通过DHCP服务器动态获取IP地址等配置信息。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 09.35.46.png" alt="截屏2020-12-21 09.35.46" style="zoom:67%;" /></p>
<h6 id="1dhcp2nip2dhcpipdhcpdiscoveripipip">（1）DHCP服务器可为主机2~主机N动态分配IP地址的最大范围是什么？主机2使用DHCP协议获取IP地址的过程中，发送的封装DHCPDiscover报文的IP分组的源IP地址和目的IP地址分别是什么？</h6>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>111.123.15.5~111.123.15.254</code></span>；</p>
<blockquote class="content-quote">
<p>111.123.15.1/24 到 111.123.15.4/24 均已被占用</p>
<p>111.123.15.0/24 是本网络地址，不可分配</p>
<p>111.123.15.255/24 是广播地址，不可分配</p>
</blockquote>
<p>主机2发送的封装DHCPDiscover报文的IP分组的源IP地址和目的IP地址分别是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0.0.0.0</code></span> 和 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>255.255.255.255</code></span>。</p>
<h6 id="22arpinternetmac2internetipmac">（2）若主机2的ARP表为空，则该主机访问Internet时，发出的第一个以太网帧的目的MAC地址是什么？封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是什么？</h6>
<ul>
<li>主机2发出的第一个以太网帧的目的MAC地址是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>ff-ff-ff-ff-ff-ff</code></span>；</li>
<li>封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>00-al-al-al-al-al</code></span>。</li>
</ul>
<h6 id="312552552550111123152wwwinternet">（3）若主机1的子网掩码和默认网关分别配置为255.255.255.0和111.123.15.2，则该主机是否能访问WWW服务器？是否能访问Internet？请说明理由。</h6>
<ul>
<li>主机1能访问WWW服务器，但不能访问Internet。</li>
<li>由于主机1的子网掩码配置正确而默认网关IP地址被错误地配置为111.123.15.2(正确IP地址是111.123.15.1)，所以主机1可以访问在同一个子网内的WWW服务器。</li>
<li>但当主机1访问Internet时，生机1发出的IP分组会被路由到错误的默认网关(111.123.15.2)，从而无法到达目的主机。</li>
</ul>
<h1 id="2014">2014真题</h1>
<h5 id="4113wpltweightrootttwpl">41、（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.48.22.png" alt="截屏2020-12-21 11.48.22" style="zoom:50%;" /></p>
<p>1）给出算法的基本设计思想；</p>
<p>2）使用C或C++语言，给出二叉树结点的数据类型定义；</p>
<p>3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。</p>
<h5 id="4210ospf42r1lsi4242r1">42、（10分）某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表及R1的接口名构造出来的网络拓扑。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.48.41.png" alt="截屏2020-12-21 11.48.41" style="zoom:50%;" /></p>
<h6 id="1_11">1）本题中的网络可抽象为数据结构中的哪种逻辑结构？</h6>
<ul>
<li>无向图</li>
</ul>
<h6 id="24242lsi42id">2）针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图（示意图中可仅以ID标识结点）。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 14.11.14.png" alt="截屏2020-12-21 14.11.14" style="zoom:50%;" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>typedef struct{
    unsigned int ID;
    unsigned int IP;
}LinkNode; //Link 的结构

typedef struct{
    unsigned int Prefix;
    unsigned int Mask;
}NetNode; //Net 的结构

typedef struct Node{
    int Flag; // Flag = 1 为 Link; Flag = 2 为 Net 

    union{
        LinkNode Lnode;
        NetNode Nnode;
    }LinkORNet;

    unsigned int Metric; 
    struct Node *next; 
}ArcNode; //弧结点

typedef struct HNode{ 
    unsigned int RouterID; 
    ArcNode *LN_link;
    Struct HNode *next; 
}HNODE; //表头结点
</code></span></code></pre>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 14.11.40.png" alt="截屏2020-12-21 14.11.40" style="zoom:50%;" /></p>
<h6 id="3dijikstrar1421921xx">3）按照迪杰斯特拉（Dijikstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 14.13.15.png" alt="截屏2020-12-21 14.13.15" style="zoom:50%;" /></p>
<h5 id="43942">43、（9分）请根据题42描述的网络，继续回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.48.41.png" alt="截屏2020-12-21 11.48.41" style="zoom:50%;" /></p>
<h6 id="142r1421921xx">1）假设路由表结构如下表所示，请给出题42图中R1的路由表，要求包括到达题42图中子网192.1.x.x的路由，且路由表中的路由项尽可能少。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.49.05.png" alt="截屏2020-12-21 11.49.05" style="zoom: 33%;" /></p>
<ul>
<li><u>因为题目要求路由表中的的路由项尽可能少</u>，所以这里可以把子网 192.1.6.0/24 和 192.1.7.0/24 聚合为子网 192.1.6.0/23。其他网络照常，可得到路由表如下：(6 分)</li>
</ul>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 14.15.16.png" alt="截屏2020-12-21 14.15.16" style="zoom:50%;" /></p>
<h6 id="21921113019217211ttl64ipr1ip19217211ipttl">2）当主机192.1.1.130向主机192.1.7.211发送一个TTL=64的IP分组时，R1通过哪个接口转发该IP分组？主机192.1.7.211收到的IP分组TTL是多少？</h6>
<ul>
<li>通过查路由表可知：R1 通过 L0 接口转发该 IP 分组。(1 分)</li>
<li>因为该分组要经过 3 个路由器(R1、R2、R4)，所以主机 192.1.7.211 收到的 IP 分组的 TTL 是 <script type="math/tex">64-3=61</script>。(1 分)</li>
</ul>
<h6 id="3r1metric10internet42r1lsi">3）若R1增加一条Metric为10的链路连接Internet，则题42表中R1的LSI需要增加哪些信息？</h6>
<ul>
<li>R1 的 LSI 需要增加一条特殊的直连网络，网络前缀 Prefix 为”0.0.0.0/0”, Metric 为 10。(1 分)</li>
</ul>
<h5 id="4412pforint-i-0-i-n-isum-aisumir1r2nr6ar3p08048100h">44、（12分）某程序中有如下循环代码段p：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>for（int i = 0; i &lt; N; i++）sum += A[i];</code></span>。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为08048100H，对应的汇编代码和机器代码如下表所示。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.49.32.png" alt="截屏2020-12-21 11.49.32" style="zoom: 45%;" /></p>
<p>OP为操作码；Rs和Rd为寄存器编号；OFFSET为偏移量，用补码表示。请回答下列问题，并说明理由。</p>
<h6 id="1m">1）M的存储器编址单位是什么？</h6>
<ul>
<li>已知计算机 M 采用 32 位定长指令字，即一条指令占 4B，观察表中各指令的地址可知， 每条指令的地址差为 4 个地址单位，即 4 个地址单位代表 4B，一个地址单位就代表了 1B， 所以该计算机是按字节编址的。(2 分)</li>
</ul>
<h6 id="2slla">2）已知sll指令实现左移功能，数组A中每个元素占多少位？</h6>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>(R2)&lt;&lt;2</code></span> 表示左移2位，即乘以4，在一个元素的地址为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>数组A的首地址 + i的值 * 4</code></span>，计算机按字节编址，因此一个元素占4B</li>
</ul>
<h6 id="344bneoffsetbnepcbne44bnebne">3）题44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne指令内容，推断出bne指令的转移目标地址计算公式。</h6>
<ul>
<li>表中bne指令的OFFSET字段的值：FFFAH，用补码表示，值为 -6</li>
<li>目标地址：<script type="math/tex">08048100H = 08048114H + 4H + OFFSET * 4 </script>
</li>
<li>
<script type="math/tex">(PC) + 4 + OFFSET * 4</script>
</li>
</ul>
<h6 id="4m5ifidexememwb3p15">4）若M采用如下“按序发射、按序完成”的5级指令流水线：IF（取值）、ID（译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件不采取任何转发措施，分支指令的执行均引起3个时钟周期的阻塞，则P中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？</h6>
<ul>
<li>由于数据相关而发生阻塞的指令为第 2、3、4、6 条，因为第 2、3、4、6 条指令都与各自前一条指令发生数据相关。(3 分)</li>
<li>第 6 条指令会发生控制冒险。(1 分)</li>
<li>当前循环的第五条指令与下次循环的第一条指令虽然有数据相关，但由于第 6 条指令后有 3 个时钟周期的阻塞，因而消除了该数据相关。(1 分)</li>
</ul>
<h5 id="4544mpmpr1r20r61000cachea">45、假设对于44题中的计算机M和程序P的机器代码，M采用页式虚拟存储管理；P开始执行时，<span style="overflow-x: auto; max-width:100%; display:inline;"><code>(R1)=(R2)=0,(R6)=1000</code></span>，其机器代码已调入主存但不在Cache中；数组A未调入主存，且所有数组元素在同一页，并存储在磁盘同一个扇区。请回答下列问题并说明理由。</h5>
<h6 id="1pr2">1）P执行结束时，R2的内容是多少？</h6>
<ul>
<li>R2 里装的是 i 的值，循环条件是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i &lt; N(1000)</code></span>，即当 i 自增到不满足这个条件时跳出循 环，程序结束，所以此时 i 的值为 1000。(1 分)</li>
</ul>
<h6 id="2mcachecachecache16cache32pcache">2）M的指令Cache和数据Cache分离。若指令Cache共有16行，Cache和主存交换的块大小为32字节，则其数据区的容量是多少？若仅考虑程序段P的执行，则<u>指令Cache</u>的命中率为多少？</h6>
<ul>
<li>指令 Cache 共有 16 行，每块 32 B，所以 Cache 数据区的容量为 <script type="math/tex">16*32B=512B</script>。 (1 分)</li>
<li>P 程序段共6条指令，<script type="math/tex">6*4B=24B<32B</script>，只占 1 块 Cache，其起始地址为 0804 8100H，对应一块的开始位置，所有的指令都在一个主存块内。</li>
<li>读取第一条指令时会发生 Cache 缺失，故将 P 所在的主存块调入 Cache 某一行，以后每次读取指令时，都能在指令 Cache 中命中。</li>
<li>因此在 1000 次循环中，只会发生 1 次指令访问缺失，所以指令 Cache 的命中率为: <script type="math/tex">(1000×6-1)/(1000×6)=99.98%</script>。 (2 分)</li>
</ul>
<h6 id="3patlb">3）P在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执行可能产生缺页异常？对于数组A的访问，需要读磁盘和TLB至少各多少次？</h6>
<ul>
<li>~~第 2 条指令，计算元素的偏移地址，执行可能发生溢出异常。~~</li>
<li>指令 4 为加法指令，即对应 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>sum += A[i]</code></span>，当数组 A 中元素的值过大时，则会导致这条 加法指令发生溢出异常；而指令 2、5 虽然都是加法指令，但他们分别为数组地址的计算指 令和存储变量 i 的寄存器进行自增的指令，而 i 最大到达 1000，所以他们都不会产生溢出异 常。(2 分)</li>
<li>只有访存指令可能产生缺页异常，即指令 3 可能产生缺页异常。(1 分)</li>
<li>因为数组 A 在磁盘的一页上，而一开始数组并不在主存中，第一次访问数组时会导致访 盘，把 A 调入内存，而以后数组 A 的元素都在内存中，则不会导致访盘，所以该程序一共 访盘一次。(2 分)</li>
<li>每访问一次内存数据就会查 TLB 一次，共访问数组 1000 次，所以此时又访问 TLB 1000 次，还要考虑到第一次访问数组 A，即访问 A[0]时，会多访问一次 TLB(第一次访问 A[0] 会先查一次 TLB，然后产生缺页，处理完缺页中断后，会重新访问 A[0]，此时又查 TLB)， 所以访问 TLB 的次数一共是 1001 次。(2 分)</li>
</ul>
<h5 id="46f2001f30">46、文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入到文件F中，作为其第30条记录。请回答下列问题，并说明理由。</h5>
<h6 id="1ff">1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F的文件控制块内容会发生哪些改变？</h6>
<ul>
<li>系统采用顺序分配方式时，插入记录需要移动其他的记录块，整个文件共有 200 条记录，要插入新记录作为第 30 条，而存储区前后均有足够的磁盘空间，且要求最少的访问存 储块数，则要把文件前 29 条记录前移，若算访盘次数移动一条记录读出和存回磁盘各是一 次访盘，29 条记录共访盘 58 次，存回第 30 条记录访盘 1 次，共访盘 59 次。(1 分)</li>
<li>F 的文件控制区的起始块号和文件长度的内容会因此改变。(1 分)</li>
</ul>
<h6 id="21kb4">2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？若每个存储块大小为1KB，其中4个字节存放链接指针，则该文件系统支持的文件最大长度是多少？</h6>
<ul>
<li>一共访盘 <strong>31</strong> 次。(1 分)<ul>
<li>文件系统采用链接分配方式时，插入记录并不用移动其他记录，只需找到相应的记录， 修改指针即可。插入的记录为其第 30 条记录，那么需要找到文件系统的第 29 块，一共需要访盘 29 次。<strong>(29次)</strong></li>
<li>然后把第 29 块的下块地址部分赋给新块，把新块存回内存会访盘 1 次<strong>(29+1)</strong></li>
<li>然后修改内存中第 29 块的下块地址字段，再存回磁盘。<strong>(29+1+1) = 31</strong></li>
</ul>
</li>
<li>4 个字节共 32 位，可以寻址 232=4G 块存储块，每块的大小为 1KB，即 1024B，其中下块地址部分占 4B，数据部分占 1020B，那么该系统的文件最大长度是 4G×1020B=4080GB。 (2 分)</li>
</ul>
<h5 id="47100010-p-vwaitsignal">47、系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>P, V(wait()，signal())</code></span> 操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>semaphore mutex1 = 1; 
semaphore mutex2 = 1; 
semaphore empty = 1000; 
semaphore full = 0; 

producer(){
    while(1){ 
        生产一个产品;
        P(empty);   //判断缓冲区是否有空位
        P(mutex2);  //互斥访问缓冲区
        把产品放入缓冲区; 
        V(mutex2);  //互斥访问缓冲区
        V(full);    //产品的数量加 1
    }
}

consumer(){ 
    while(1){
        P(mutex1);
        for(int i = 0; i &lt;= 10; ++i){
            P(mutex2); //互斥访问缓冲区 
            从缓冲区取出一件产品;
            V(mutex2); //互斥访问缓冲区 
            V(empty);  //腾出一个空位
            消费这件产品;
        }
        V(mutex1);
    }
} 
</code></span></code></pre>
<h1 id="2013">2013真题</h1>
<h5 id="41-a-0-5-5-3-5-7-5-5-5-a-0-5-5-3-5-1-5-7-aana-1">41、例如 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>A = (0, 5, 5, 3, 5, 7, 5, 5)</code></span> , 侧5为主元素；又如 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>A = (0, 5, 5, 3, 5, 1, 5, 7)</code></span> ，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：</h5>
<p>（1）给出算法的基本设计思想。</p>
<p>（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。</p>
<h5 id="42104s-do-for-repeat-whilep1035-p2015-p3015p4035s422">42、（10分）设包含4个数据元素的集合<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S = {"do", "for", "repeat", "while"}</code></span>，各元素的查找概率依次为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>p1=0.35, p2=0.15, p3=0.15，p4=0.35</code></span>。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：</h5>
<p>（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？</p>
<p>（2）若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？</p>
<h5 id="43932cpu800mhzcachecpi4cache3283240ns32200mhz3232">43、（9分）某32位计算机，CPU主频为800MHz，Cache命中时的CPI为4，Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns；存储器总线宽度为32位，总线时钟频率为200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。</h5>
<h6 id="1cpu">（1）CPU和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？</h6>
<ul>
<li>CPU的时钟周期：<script type="math/tex">\cfrac{1}{800MHz}=0.00125\mu s=1.25ns</script>
</li>
<li>总线的时钟周期：<script type="math/tex">\cfrac{1}{200MHz}=0.005\mu s=5ns</script>
</li>
<li>存储器总线宽度为32位，即4B，总线的带宽（即最大数据传输率）为：800M/s</li>
</ul>
<h6 id="2cache">（2）Cache缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？</h6>
<ul>
<li>Cache块大小为 <script type="math/tex">32B</script>
</li>
<li>主存采用 8 体交叉存储方式，每个体的存储字长为 <script type="math/tex">32bit=4B</script>，共 <script type="math/tex">8*4=32B</script>
</li>
<li>因此 Cache 缺失时需要一个读突发传送总线事务读取一个主存块。(1 分)</li>
</ul>
<h6 id="3_2">（3）存储器总线完成一次读突发传送总线事务所需的时间是多少？</h6>
<blockquote class="content-quote">
<p>“每次突发传送 <script type="math/tex">32B</script>，传送地址 或 <script type="math/tex">32bit</script> 数据均需要一个总线时钟周期。”</p>
</blockquote>
<ul>
<li>
<script type="math/tex">32B</script> 数据，需要1个时钟周期传送地址，8个时钟周期传送 <script type="math/tex">32*8=256bit=32B</script> 数据</li>
<li>主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns；每隔 <script type="math/tex">40 ns/8 = 5 ns</script> 启动一个体工作（各进行 1 次存取），第一个体读数据花费 40 ns，之后数据存取与数据传输重叠；用 8 个总线时钟周期传输数据。</li>
<li>读突发传送总线事务时间：<script type="math/tex">5 ns(传送地址) + 40ns + 8×5 ns(传送数据) = 85 ns</script>。(2 分)</li>
</ul>
<h6 id="4bp10012cache5bpcpu">（4）若程序BP执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache缺失率为5%，不考虑替换等开销，则BP的CPU执行时间是多少？</h6>
<ul>
<li>BP的CPU执行时间：命中时的指令执行时间 + Cache 缺失时的额外开销</li>
<li>Cache命中时的CPI为4，命中时的指令执行时间：<script type="math/tex">100×4×1.25 ns = 500 ns</script>。</li>
<li>指令执行过程中 Cache 缺失时的额外开销：<script type="math/tex">1.2×100×5%×85 ns = 510 ns</script>。</li>
<li>BP 的 CPU 执行时间：<script type="math/tex">500 ns+510 ns=1 010 ns</script>。(2 分)</li>
</ul>
<h5 id="441416cpucfzfnf00000-op-cz-n-cfzf-nf-1-1-c1z0n1-cf-nf-cf1-nf1-offset-pc22offset-pc2">44、（14分）某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位/借位标志CF、零标志ZF和符号标志NF。假定为该机设计了条件转移指令，其格式如下，其中，00000 为操作码 OP; C、Z 和 N 分别为 CF、ZF 和 NF 的对应检测位，某检测位为 1 时表示需检测对应标志，需检测的标志位中只要有一个为 1 就转移，否则不转移，例如，若 C=1，Z=0，N=1，则需检测 CF 和 NF 的值，当 CF=1 或 NF=1 时发生转移; OFFSET 是相对偏移量，用补码表示。转移执行时，转移目标地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2+2×OFFSET</code></span> ; 顺序执行时，下条指令地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2</code></span>。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.50.38.png" alt="截屏2020-12-21 11.50.38" style="zoom: 33%;" /></p>
<h6 id="1_12">（1）该计算机存储器按字节编址还是按字编址？该条件转移指令向后（反向）最多可跳转多少条指令？</h6>
<ul>
<li>计算机采用16位定长指令字格式，顺序执行时，下条指令地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2</code></span>，因此，该计算机存储器按字节编址。</li>
<li>该条件转移指令向后（反向）最多可跳转多少条指令：<ul>
<li>OFFSET的取值范围为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>-128 ~ 127</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>(PC)+2+2×OFFSET = (PC)+2×(1+OFFSET)</code></span>：1+OFFSET 的取值范围为：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>-127 ~ 128</code></span></li>
<li>故相对于当前条件转移指令，<strong>向后</strong> 最多可跳转 127 条指令。</li>
</ul>
</li>
</ul>
<h6 id="2200chcf0zf0nf1pccf1zf0nf0pc">（2）某条件转移指令的地址为200CH，指令内容如下图所示，若该指令执行时CF=0，ZF=0，NF=1，则该指令执行后PC的值是多少？若该指令执行时CF=1，ZF=0，NF=0，则该指令执行后PC的值又是多少？请给出计算过程。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.52.49.png" alt="截屏2020-12-21 11.52.49" style="zoom: 33%;" /></p>
<ul>
<li>若该指令执行时CF=0，ZF=0，NF=1，则需要跳转<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>OFFSET = 11100011 = -(0011101) = -29</code></span></li>
<li>该指令执行后PC的值是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>200CH + 2 + 2*(-29) = 200CH - 38H = 1FD4H</code></span></li>
</ul>
</li>
<li>若该指令执行时CF=1，ZF=0，NF=0，则不需要跳转，<ul>
<li>该指令执行后PC的值是 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>200EH</code></span></li>
</ul>
</li>
</ul>
<h6 id="3czn">（3）实现“无符号数比较小于等于时转移”功能的指令中，C、Z和N应各是什么？</h6>
<ul>
<li>进位/借位标志CF、零标志ZF和符号标志NF。</li>
<li>C=1, Z=1, N=0 (3 分)</li>
</ul>
<h6 id="413">（4）以下是该指令对应的数据通路示意图，要求给出图中部件1~3的名称或功能说明。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.53.03.png" alt="截屏2020-12-21 11.53.03" style="zoom: 33%;" /></p>
<ul>
<li>部件1：指令寄存器(用于存放当前指令)；</li>
<li>部件2：移位寄存器(用于左移一位)；</li>
<li>部件3：加法器(地址相加)。(3 分)</li>
<li></li>
</ul>
<h5 id="457500pvwaitsignal">45、（7分）某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：请添加必要的信号量和P、V（或wait（）、signal（）操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>cobegin
参观者进程 i:
{
   „
   进门;
   „
   参观;
   „
   出门;
   „
}
coend
</code></span></code></pre>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>Semaphore empty = 500;  // 博物馆可以容纳的最多人数(2 分)
Semaphore mutex = 1;    // 用于出入口资源的控制(2 分)

cobegin
参观者进程 i:
{
    P(empty);
    P(mutex);
    进门;
    V(mutex);

    参观;

    P(mutex);
    出门;
    V(mutex);
    V(empty);
}
coend
</code></span></code></pre>
<h5 id="468324">46、（8分）某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。</h5>
<h6 id="1_13">（1）若使用一级页表的分页存储管理方式，则页的大小是多少字节？页表最大占用多少字节？</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.54.25.png" alt="截屏2020-12-21 11.54.25" style="zoom:40%;" /></p>
<ul>
<li>若使用一级页表的分页存储管理方式：<ul>
<li>计算机按字节编址。</li>
<li>页的大小为：<script type="math/tex">2^{12}*1B=4KB</script>
</li>
</ul>
</li>
<li>页表最大占用多少字节：<ul>
<li>页表项数为 <script type="math/tex">2^{32}/4K=2^{20}</script>
</li>
<li>页表项大小为 <script type="math/tex">4B</script>
</li>
<li>该一级页表最大为 <script type="math/tex">2^{20}×4B=4MB</script>。(2 分)</li>
</ul>
</li>
</ul>
<h6 id="2la">（2）若使用二级页表的分页存储管理方式，设逻辑地址为LA，请分别给出其对应的页目录号和页表索引的表达式。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.54.53.png" alt="截屏2020-12-21 11.54.53" style="zoom:40%;" /></p>
<ul>
<li>页目录号可表示为：( ( ( unsigned int ) ( LA ) ) &gt;&gt; 22 ) &amp; 0x3FF。(1 分) </li>
<li>页表索引可表示为：( ( ( unsigned int ) ( LA ) ) &gt;&gt; 12 ) &amp; 0x3FF。(1 分)</li>
</ul>
<h6 id="3100008000h8kb00900000h00200000h2">（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H，其长度为8KB，被装载到从物理地址00900000H开始的连续主存空间中。页表从主存00200000H开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面2的起始物理地址。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.55.06.png" alt="截屏2020-12-21 11.55.06" style="zoom:40%;" /></p>
<ul>
<li>代码段的起始逻辑地址： <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[00008][000]H</code></span><ul>
<li>页号：8</li>
<li>页内偏移：0</li>
</ul>
</li>
<li>求物理地址1：<script type="math/tex">0020 0000H + 8*\cfrac{页表项大小4B}{按B编址} = 0020 0020H</script>
</li>
<li>求物理地址2：<script type="math/tex">0020 0024H</script>
</li>
<li>求物理地址3<ul>
<li>代码段起始物理地址 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>00900000H</code></span>，代码段长度为 <script type="math/tex">8KB=2^{13}B</script>，一半就是 <script type="math/tex">4KB</script>
</li>
<li>
<script type="math/tex">4KB = 2^{12}</script>，则偏移为 <script type="math/tex">FFFH</script>
</li>
<li>求物理地址3： <script type="math/tex">00901000H</script>
</li>
</ul>
</li>
<li>页框号1：<script type="math/tex">[0090\ 0]H</script>
</li>
<li>页框号2：<script type="math/tex">[0090\ 1]H</script>
</li>
</ul>
<h5 id="479internet47asir1as2r2r33r2r1r3ip47">47、（9分）假设Internet的两个自治系统构成的网络如题47图所示，自治系统ASI由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口IP地址如题47图所示。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.55.23.png" alt="截屏2020-12-21 11.55.23" style="zoom:40%;" /></p>
<h6 id="1r247">（1）假设路由表结构如下表所示。<u>请利用路由聚合技术</u>，给出R2的路由表，要求包括到达题47图中所有子网的路由，且路由表中的路由项尽可能少。</h6>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.55.42.png" alt="截屏2020-12-21 11.55.42" style="zoom:40%;" /></p>
<p><u>请利用路由聚合技术</u></p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>目的网络</th>
<th>下一跳</th>
<th>接口</th>
</tr>
</thead>
<tbody>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>153.14.5.0/24</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>153.14.3.2</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S0</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>194.17.20.128/25</code></span></td>
<td>无</td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>E0</code></span></td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>194.17.20.0/23</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>194.17.24.2</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>S1</code></span></td>
</tr>
</tbody>
</table></div>
<h6 id="2r2ip-1941720200-ipr2ip">（2）若R2收到一个目的IP地址为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>194.17.20.200</code></span> 的IP分组，R2会通过哪个接口转发该IP分组？</h6>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>200 = 1100 1000</code></span></p>
<ul>
<li>该 IP 分组的目的 IP 地址 194.17.20.200 与路由表中 194.17.20.0/23 和 194.17.20.128/25 两个路由表项均匹配，<u>根据最长匹配原则</u>，R2 将通过 E0 接口转发该 1P 分组。(1 分)</li>
</ul>
<h6 id="3r1r2">（3）R1与R2之间利用哪个路由协议交换路由信息？该路由协议的报文被封装到哪个协议的分组中进行传输？</h6>
<ul>
<li>R1 与 R2 之间利用 BGP4(或 BGP)交换路由信息；(1 分)</li>
<li>BGP4 的报文被封装到 TCP 协议段中进行传输。(1 分)</li>
</ul>
<p>若考生解答为 EGP 协议，且正确解答 EGP 采用 IP 协议进行通信，亦给分。</p>
<h1 id="2012">2012真题</h1>
<h5 id="416abcdef1035405060200561">41、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请问答下列问题。</h5>
<p>1）给出完整的合并过程，并求出最坏情况下比较的总次数。</p>
<p>2）根据你的合并过程，描述N（N≥2）个不等长升序表的合并策略，并说明理由。</p>
<h5 id="42loadingbeingstr1str2str1str2ip">42、假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.56.20.png" alt="截屏2020-12-21 11.56.20" style="zoom:40%;" /></p>
<p>1）给出算法的基本设计思想。</p>
<p>2）根据设计思想，采用C或C++或JAVA语音描述算法，关键之处给出注释。</p>
<p>3）说明你所设计算法的时间复杂度。</p>
<h5 id="43cpu80mhzcpi415cache516bcache9932">43、假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，主存与Cache之间5交换的块大小为16B，Cache的命中率为99%，存储器总线宽带为32位。请回答下列问题。</h5>
<p>1）该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求？</p>
<p>2）假定在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，则CPU平均每秒产生多少次缺页异常？若页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时DMA传送采用周期挪用方式，磁盘I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA请求次数至少是多少？</p>
<p>3）CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什么？</p>
<p>4）为了提高性能，主存采用4体低位交叉存储模式，工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少？</p>
<h5 id="4416cachecache44rsrdmemxxx5ifidexmwb">44、某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，（x）表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.56.49.png" alt="截屏2020-12-21 11.56.49" style="zoom: 33%;" /></p>
<p>1）若int型变量x的值为-513，存放在寄存器R1中，则执行指令“SHLR1”后，R1的内容是多少？（用十六进制表示）</p>
<p>2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？</p>
<p>3）若高级语言程序中某赋值语句为x=a+b，x、a和b均为int型变量，它们的存储单元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。则这4条指令执行过程中，I3的ID段和I4的IF段被阻塞的原因各是什么？</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.57.16.png" alt="截屏2020-12-21 11.57.16" style="zoom:40%;" /></p>
<p>4）若高级语言程序中某赋值语句为x=x*2+a，x和a均为unsignedint类型变量，它们的存储单元6地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。</p>
<h5 id="450532152141p11320406111013214">45、某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的&lt;虚拟页号，访问时刻&gt;是：&lt;1，1&gt;、&lt;3，2&gt;、&lt;0，4&gt;、&lt;0，6&gt;、&lt;1，11&gt;、&lt;0，13&gt;、&lt;2，14&gt;。请回答下列问题。</h5>
<p>1）访问&lt;0，4&gt;时，对应的页框号是什么？</p>
<p>2）访问&lt;1，11&gt;时，对应的页框号是什么？说明理由。</p>
<p>3）访问&lt;2，14&gt;时，对应的页框号是什么？说明理由。</p>
<p>4）该策略是否适合于时间局部性好的程序？说明理由。</p>
<h5 id="464tb1tb2401kbfcb512b">46、某文件系统空间的最大容量为4TB（1TB=240），以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。</h5>
<p>1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？</p>
<p>2）假设索引表区采用如下结构：第0~7字节采用&lt;起始块号，块数&gt;格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。</p>
<h5 id="47hinternetip19216808sip211687180hstcph5ip47-a">47、主机H通过快速以太网连接Internet，IP地址为192.168.0.8，服务器S的IP地址为211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.57.36.png" alt="截屏2020-12-21 11.57.36" style="zoom:40%;" /></p>
<p>1）题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？</p>
<p>2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？</p>
<p>3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所示，则该IP分组到达H时经过了多少个路由器？</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.58.22.png" alt="截屏2020-12-21 11.58.22" style="zoom:40%;" /></p>
<h1 id="2011">2011真题</h1>
<h5 id="418605ga">41、（8分）已知有6个顶点（顶点编号为0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。要求：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.59.07.png" alt="截屏2020-12-21 11.59.07" style="zoom:40%;" /></p>
<p>（1）写出图G的邻接矩阵A。</p>
<p>（2）画出有向带权图G。</p>
<p>（3）求图G的关键路径，并计算该关键路径的长度。</p>
<h5 id="4215ll1sl2ss11113151719s115s2246820s1s211abab">42、（15分）一个长度为L（L≥1）的升序序列S，处在第L/2个位置的数称为S的中位数。例如，若序列S1=（11，13，15，17，19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：</h5>
<p>（1）给出算法的基本设计思想。</p>
<p>（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。</p>
<h5 id="43118c88r1r8xymnz1z2k1k2">43、（11分）假定在一个8位字长的计算机中运行如下类C程序段：若编译器编译时将8个8位寄存器R1~R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示）</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.59.35.png" alt="截屏2020-12-21 11.59.35" style="zoom:40%;" /></p>
<p>（1）执行上述程序段后，寄存器R1、R5和R6的内容分别是什么？（用十六进制表示）</p>
<p>（2）执行上述程序段后，变量m和k1的值分别是多少？（用十进制表示）</p>
<p>（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器辅助电路实现？简述理由。</p>
<p>（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？</p>
<h5 id="441216mb1mb4kbcache8cache32bcache44-a44-b">44、（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。请回答下列问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 11.59.55.png" alt="截屏2020-12-21 11.59.55" style="zoom:40%;" /></p>
<p>（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？</p>
<p>（2）使用物理地址访问Cache时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。</p>
<p>（3）虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。</p>
<p>（4）假定为该机配置一个4路组相联的TLB共可存放8个页表项，若其当前内容（十六进制）如题44-c图所示，则此时虚拟地址024BACH所在的页面是否存在主存中？要求说明理由。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.00.16.png" alt="截屏2020-12-21 12.00.16" style="zoom:40%;" /></p>
<h5 id="458110pvwaitsignal">45、（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：请添加必要的信号量和P、V（或wait（）、signal（））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.00.45.png" alt="截屏2020-12-21 12.00.45" style="zoom:40%;" /></p>
<h5 id="467">46、（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。</h5>
<p>（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？</p>
<p>（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。</p>
<h5 id="479mac00-15-c5-c1-5e-28ip10212810047-a47-bweb180ascii">47、（9分）某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个字节的十六进制及ASCII码内容。请参考图中的数据回答以下问题。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.01.10.png" alt="截屏2020-12-21 12.01.10" style="zoom:40%;" /></p>
<p>（1）Web服务器的IP地址是什么？该主机的默认网关的MAC地址是什么？</p>
<p>（2）该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址？封装该协议请求报文的以太网帧的目的MAC地址是什么？</p>
<p>（3）假设HTTP/1.1协议以持续的非流水线方式工作，一次请求-响应时间为RTT，rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT？</p>
<p>（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段？注：以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.01.31.png" alt="截屏2020-12-21 12.01.31" style="zoom: 33%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.07.50.png" alt="截屏2020-12-21 12.07.50" style="zoom:40%;" /></p>
<h1 id="2010">2010真题</h1>
<h5 id="4110783011189140hkeykeyx3mod707">41、（10分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H（key）=（keyx3）MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。</h5>
<p>（1）请画出所构造的散列表。</p>
<p>（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。</p>
<h5 id="4213nn1rrp0pnrx0x1xn-1xpxp1xn-1x0x1xp-1">42、（13分）设将n（n&gt;1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0&lt;p&lt;n）个位置，即将R中的数据由（X0，X1&hellip;Xn-1）变换为（Xp，Xp+1&hellip;Xn-1，X0，X1&hellip;Xp-1）。要求：</h5>
<p>（1）给出算法的基本设计思想。</p>
<p>（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。</p>
<p>（3）说明你所设计算法的时间复杂度和空间复杂度。</p>
<h5 id="431116128kb">43、（11分）某计算机字长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如下：转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：请回答下列问题：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.02.03.png" alt="截屏2020-12-21 12.02.03" style="zoom:40%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.02.53.png" alt="截屏2020-12-21 12.02.53" style="zoom:40%;" /></p>
<p>（1）该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？</p>
<p>（2）转移指令的目标地址范围是多少？</p>
<p>（3）若操作码0010B表示加法操作（助记符为add），寄存器R4和R5的编号分别为100B和101B，R4的内容为1234H，R5的内容为5678H，地址1234H中的内容为5678H，地址5678H中的内容为1234H，则汇编语言为“add（R4），（R5）+”（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元中的内容会改变？改变后的内容是什么？</p>
<h5 id="4412256mbcachecache8cachecache64bcacheabint32ijsuma320">44、（12分）某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：假定int类型数据用32位补码表示，程序编译时i，j，sum均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.05.15.png" alt="截屏2020-12-21 12.05.15" style="zoom:40%;" /></p>
<p>（1）若不考虑用于cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？</p>
<p>（2）数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？</p>
<p>（3）程序A和B的数据访问命中率各是多少？哪个程序的执行时间更短？</p>
<h5 id="457cscan2kb16384">45、（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。</h5>
<p>（1）请说明在上述条件下如何进行磁盘块空闲状态的管理。</p>
<p>（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图所示），磁道号请求队列为50，90，30，120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区点共需要多少时间？要求给出计算过程。</p>
<p>（3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.05.29.png" alt="截屏2020-12-21 12.05.29" style="zoom:40%;" /></p>
<h5 id="46864kb6page1kb4pageframe26026017cah">46、（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.05.46.png" alt="截屏2020-12-21 12.05.46" style="zoom:40%;" /></p>
<p>（1）该逻辑地址对应的页号是多少？</p>
<p>（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。</p>
<p>（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下）。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.06.04.png" alt="截屏2020-12-21 12.06.04" style="zoom:40%;" /></p>
<h5 id="479csmacd10mbps2km200000kms">47、（9分）某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10Mbps，主机甲和主机乙之间的距离为2km，信号传播速度是200000km/s。请回答下列问题，要求说明理由或写出计算过程。</h5>
<p>（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）？</p>
<p>（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？</p>
<h1 id="2009">2009真题</h1>
<h5 id="4110">41、（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：</h5>
<p>1设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；</p>
<p>2选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；</p>
<p>3重复步骤2，直到u是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。</p>
<h5 id="4215listkkdata10">42、（15分）已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.06.36.png" alt="截屏2020-12-21 12.06.36" style="zoom:40%;" /></p>
<p>（1）描述算法的基本设计思想；</p>
<p>（2）描述算法的详细实现步骤；</p>
<p>（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。</p>
<h5 id="438cpu500mhzcpi5505mbs32182">43、（8分）某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。</h5>
<p>1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？</p>
<p>2）当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（假设DMA与CPU之间没有访存冲突）</p>
<h5 id="4413161610mdrine1dbmdrmdrin1mdrmaraddr1r0r0r1r1r0r1r1">44、（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD（R1），R0”的功能为（R0）+（（R1））（R1），即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格..列出指令执行阶段每个节拍的功能和有效控制信号。</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.08.58.png" alt="截屏2020-12-21 12.08.58" style="zoom:40%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.09.26.png" alt="截屏2020-12-21 12.09.26" style="zoom:40%;" /></p>
<h5 id="457p1p2p3nn0p1produceputp2getoddcountoddp3getevencounteven">45、（7分）三个进程P1、P2、P3互斥使用一个包含N（N&gt;0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。</h5>
<h5 id="4684kb100nstlb10ns108nstlb2lru1tlb2tlbtlbtlb302362h1565h25a5h">46、（8分）请求分页管理系统中，假设某进程的页表内容如下表所示：页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设1TLB初始为空；2地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；3有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.09.45.png" alt="截屏2020-12-21 12.09.45" style="zoom:40%;" /></p>
<p>（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。</p>
<p>（2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。</p>
<h5 id="479r1e1e212l0r2r2r1l0ip20211821r2l0ip20211822l1ip130111201e0ip20211831ip20211832r1r2">47、（9分）某网络拓扑如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1；R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。R1和R2的路由表结构为：</h5>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.09.53.png" alt="截屏2020-12-21 12.09.53" style="zoom:40%;" /></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机真题.assets/截屏2020-12-21 12.10.09.png" alt="截屏2020-12-21 12.10.09" style="zoom:40%;" /></p>
<p>（1）将IP地址空间202.118.1.0/24划分为2个子网，分别分配给局域网1、局域网2，每个局域网需分配的IP地址数不少于120个。请给出子网划分结果，说明理由或给出必要的计算过程。</p>
<p>（2）请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。</p>
<p>（3）请采用路由聚合技术，给出R2到局域网1和局域网2的路由。</p>
  </div>
</div>
 
    </div>
  </div>
  <div id="footer-background">
    <div id="footer">
      <div class="legal pure-g">
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-license"><a href="https://beian.miit.gov.cn/#/Integrated/index">浙ICP备2020038748号</a></p>
  </div>
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-links"><a href="https://github.com/zromyk">GitHub</a></p>
    <p class="legal-copyright">Copyright © 2021 Wei Zhou. 保留所有权利。</p>
  </div>
</div>
    </div>
  </div>
  <!-- <script src="https://cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script> -->
  <script src="/style/html/jquery.min.js"></script>
  <script src='/style/article/latex/latest.js?config=TeX-MML-AM_CHTML'></script>
<!-- <script src="https://cdn.geogebra.org/apps/deployggb.js"></script> -->
<script src="/style/article/deployggb.js"></script>
<!-- <script src="https://apps.bdimg.com/libs/highlight.js/9.1.0/highlight.min.js"></script> -->
<script type="text/javascript">
  // 脚本：navigation 随鼠标移动自动变换宽度
  var element = document.getElementById("navigation"); // 获取要操作的元素
  var elementWidth = parseInt(getComputedStyle(element).width);
  var elementLeft = 0;
  var elementRight = 0;
  element.addEventListener('mouseenter', function (event) { // 添加鼠标按下事件的监听器
    elementLeft = element.getBoundingClientRect().left - 10;
    elementRight = element.getBoundingClientRect().left + elementWidth * 3;
    window.addEventListener('mousemove', resize); // 添加全局的鼠标移动事件的监听器
  });

  function resize(event) {
    var minWidth = elementWidth;
    var maxWidth = elementWidth * 2.5;
    // console.log(elementLeft, event.clientX, elementRight, event.clientX - elementLeft + elementWidth / 2);
    if (elementLeft <= event.clientX && event.clientX <= elementRight) {
      var width = event.clientX - elementLeft + elementWidth / 2;
      width = Math.min(width, maxWidth);
      width = Math.max(width, minWidth);
      element.style.width = width + 'px'; // 设置新的宽度样式属性
    }
    else {
      element.style.width = elementWidth + 'px'; // 设置新的宽度样式属性
      stopResize();
    }
  }

  function stopResize() {
    element.style.width = elementWidth + 'px'; // 设置新的宽度样式属性
    // console.log("stopResize", elementLeft, event.clientX, elementRight, event.clientX - elementLeft + elementWidth / 2);
    window.removeEventListener('mousemove', resize); // 移除鼠标移动事件的监听器
  }
</script>
<script src="/style/article/highlight/highlight.min.js"></script>
<script type="text/javascript">
  // 脚本：code语法高亮
  hljs.initHighlightingOnLoad();
</script>
<script>
  function animateByNav() {
    $("html").animate({
        scrollTop: ($(event.target.hash).offset().top - 52)
    }, 300);
  };
</script>
<script src="/style/article/pell-1.0.6/dist/pell.js"></script>
<script>
  // 脚本：自由编辑页面
  var editor = window.pell.init({
    element: document.getElementById('editor'),
    defaultParagraphSeparator: 'p',
    onChange: function(html) {
        document.getElementById('text-output').innerHTML = html
        document.getElementById('html-output').textContent = html
    }
  });

  function markdownEditor() {
    var articles = document.getElementById('content-articles-markdown');
    if (articles.getAttribute("contenteditable") == "true") {
        articles.setAttribute("contenteditable", "false");
        document.getElementById("content-articles-markdownEditor").style.display = "none"; //隐藏
        document.getElementById("button-markdownEditor").innerHTML = "启用编辑";
    } else {
        articles.setAttribute("contenteditable", "true");
        document.getElementById("content-articles-markdownEditor").style.display = ""; //显示
        document.getElementById("button-markdownEditor").innerHTML = "关闭编辑";
    }
  };

  function save() {
      window.alert("保存成功");
  };
</script>

</body>
</html>
